The enzyme methyl-coenzyme M reductase (MCR) plays an important role in mediating global levels of methane by catalyzing a reversible reaction that leads to the production or consumption of this potent greenhouse gas in methanogenic and methanotrophic archaea. In methanogenic archaea, the alpha subunit of MCR (McrA) typically contains four to six posttranslationally modified amino acids near the active site. Recent studies have identified enzymes performing two of these modifications (thioglycine and 5-[S]-methylarginine), yet little is known about the formation and function of the remaining posttranslationally modified residues. Here, we provide in vivo evidence that a dedicated S-adenosylmethionine-dependent methyltransferase encoded by a gene we designated methylcysteine modification (mcmA) is responsible for formation of S-methylcysteine in Methanosarcina acetivorans McrA. Phenotypic analysis of mutants incapable of cysteine methylation suggests that the S-methylcysteine residue might play a role in adaption to mesophilic conditions. To examine the interactions between the S-methylcysteine residue and the previously characterized thioglycine, 5-(S)-methylarginine modifications, we generated M. acetivorans mutants lacking the three known modification genes in all possible combinations. Phenotypic analyses revealed complex, physiologically relevant interactions between the modified residues, which alter the thermal stability of MCR in a combinatorial fashion that is not readily predictable from the phenotypes of single mutants. High-resolution crystal structures of inactive MCR lacking the modified amino acids were indistinguishable from the fully modified enzyme, suggesting that interactions between the posttranslationally modified residues do not exert a major influence on the static structure of the enzyme but rather serve to fine-tune the activity and efficiency of MCR.