Despite considerable effort, no physical mechanism has been experimentally shown to explain the N-terminal codon bias in prokaryotic genomes. Using a systematic study of synonymous substitutions in two endogenous E. coli genes, we show that interactions between the coding region and the upstream Shine-Dalgarno sequence modulate both the rate of mRNA degradation and the efficiency of translation-initiation via a ’ribosome-protection’ mechanism, which ultimately affects cellular fitness. We further demonstrate that occlusion of the Shine-Dalgarno sequence depends on the formation of non-equilibrium secondary structures, which may include long-range contacts, highlighting the role of co-transcriptional mRNA folding and the influence of the 5’-untranslated region in determining the optimal coding sequence. Finally, a statistical analysis of the E. coli genome also specifically implicates avoidance of intra-molecular base-pairing with the Shine-Dalgarno sequence. Our results therefore provide general physical insights into the coding-level sequence features that optimize protein expression in prokaryotes.