The genetic code is virtually universal in biology and was likely established before the advent of cellular life. The extent to which mistranslation occurs is poorly understood and presents a fundamental question in basic research and production of recombinant proteins. Here we used shotgun proteomics combined with unbiased protein modification analysis to quantitatively analyze in vivo mistranslation in an E. coli strain with a defect in the editing mechanism of leucyl-tRNA synthetase. We detected the misincorporation of a non-proteinogenic amino acid norvaline on 10% of all measured leucine residues under microaerobic conditions and revealed preferential deployment of a tRNA(Leu)(CAG) isoacceptor during norvaline misincorporation. The strain with the norvalylated proteome demonstrated a substantial reduction in cell fitness under both prolonged aerobic and microaerobic cultivation. Unlike norvaline, isoleucine did not substitute for leucine even under harsh error-prone conditions. Our study introduces shotgun proteomics as a powerful tool in quantitative analysis of mistranslation.