Expanding the genetic code is an important aim of synthetic biology, but some organisms developed naturally expanded genetic codes long ago over the course of evolution. Less than 1% of all sequenced genomes encode an operon that reassigns the stop codon UAG to pyrrolysine (Pyl), a genetic code variant that results from the biosynthesis of Pyl-tRNA(Pyl). To understand the selective advantage of genetically encoding more than 20 amino acids, we constructed a markerless tRNA(Pyl) deletion strain of Methanosarcina acetivorans (ΔpylT) that cannot decode UAG as Pyl or grow on trimethylamine. Phenotypic defects in the ΔpylT strain were evident in minimal medium containing methanol. Proteomic analyses of wild type (WT) M. acetivorans and ΔpylT cells identified 841 proteins from >7,000 significant peptides detected by MS/MS. Protein production from UAG-containing mRNAs was verified for 19 proteins. Translation of UAG codons was verified by MS/MS for eight proteins, including identification of a Pyl residue in PylB, which catalyzes the first step of Pyl biosynthesis. Deletion of tRNA(Pyl) globally altered the proteome, leading to >300 differentially abundant proteins. Reduction of the genetic code from 21 to 20 amino acids led to significant down-regulation in translation initiation factors, amino acid metabolism, and methanogenesis from methanol, which was offset by a compensatory (100-fold) up-regulation in dimethyl sulfide metabolic enzymes. The data show how a natural proteome adapts to genetic code reduction and indicate that the selective value of an expanded genetic code is related to carbon source range and metabolic efficiency.