Pyrrolysine (Pyl), the 22nd proteogenic amino acid, was restricted until recently to few organisms. Its translational use necessitates the presence of enzymes for synthesizing it from lysine, a dedicated amber stop codon suppressor tRNA, and a specific aminoacyl tRNA synthetase. The three genomes of the recently proposed Thermoplasmata-related 7th order of methanogens contain the complete genetic set for Pyl synthesis and its translational use. Here, we have analyzed the genomic features of the Pyl-coding system in these three genomes with those previously known from Bacteria and Archaea and analyzed the phylogeny of each component. This shows unique peculiarities, notably an amber tRNA(Pyl) with an imperfect anticodon stem and a shortened tRNA(Pyl) synthetase. Phylogenetic analysis indicates that a Pyl-coding system was present in the ancestor of the seventh order of methanogens and appears more closely related to Bacteria than to Methanosarcinaceae, suggesting the involvement of lateral gene transfer in the spreading of pyrrolysine between the two prokaryotic domains. We propose that the Pyl-coding system likely emerged once in Archaea, in a hydrogenotrophic andmethanol-H-2-dependent methylotrophic methanogen. The close relationship between methanogenesis and the Pyl system provides a possible example of expansion of a still evolving genetic code, shaped by metabolic requirements.