We used a phylogenetic approach to analyze the evolution of methanogenesis and methanogens. We show that 23 vertically transmitted ribosomal proteins do not support the monophyly of methanogens, and propose instead that there are two distantly related groups of extant archaea that produce methane, which we have named Class I and Class II. Based on this finding, we subsequently investigated the uniqueness of the origin of methanogenesis by studying both the enzymes of methanogenesis and the proteins that synthesize its specific coenzymes. We conclude that hydrogenotrophic methanogenesis appeared only once during evolution. Genes involved in the seven central steps of the methanogenic reduction of carbon dioxide (CO2) are ubiquitous in methanogens and share a common history. This suggests that, although extant methanogens produce methane from various substrates (CO2, formate, acetate, methylated C-1 compounds), these archaea have a core of conserved enzymes that have undergone little evolutionary change. Furthermore, this core of methanogenesis enzymes seems to originate (as a whole) from the last ancestor of all methanogens and does not appear to have been horizontally transmitted to other organisms or between members of Class I and Class II. The observation of a unique and ancestral form of methanogenesis suggests that it was preserved in two independent lineages, with some instances of specialization or added metabolic flexibility. It was likely lost in the Halobacteriales, Thermoplasmatales and Archaeoglobales. Given that fossil evidence for methanogenesis dates back 2.8 billion years, a unique origin of this process makes the methanogenic archaea a very ancient taxon.