Synonymous mutations do not alter the specified amino acid but may alter the structure or function of an mRNA in ways that impact fitness. There are few examples in the literature, however, in which the effects of synonymous mutations on microbial growth rates have been measured, and even fewer for which the underlying mechanism is understood. We evolved four populations of a strain of Salmonella enterica in which a promiscuous enzyme has been recruited to replace an essential enzyme. A previously identified point mutation increases the enzyme's ability to catalyze the newly needed reaction (required for arginine biosynthesis) but decreases its ability to catalyze its native reaction (required for proline biosynthesis). The poor performance of this enzyme limits growth rate on glucose. After 260 generations, we identified two synonymous mutations in the first six codons of the gene encoding the weak-link enzyme that increase growth rate by 41 and 67%. We introduced all possible synonymous mutations into the first six codons and found substantial effects on growth rate; one doubles growth rate, and another completely abolishes growth. Computational analyses suggest that these mutations affect either the stability of a stem-loop structure that sequesters the start codon or the accessibility of the region between the Shine-Dalgarno sequence and the start codon. Thus, these mutations would be predicted to affect translational efficiency and thereby indirectly affect mRNA stability because translating ribosomes protect mRNA from degradation. Experimental data support these hypotheses. We conclude that the effects of the synonymous mutations are due to a combination of effects on mRNA stability and translation efficiency that alter levels of the weak-link enzyme. These findings suggest that synonymous mutations can have profound effects on fitness under strong selection and that their importance in evolution may be under-appreciated.