Anaerobic methane metabolism is among the hallmarks of Archaea, originating very early in their evolution. Here, we show that the ancestor of methane metabolizers was an autotrophic CO
-reducing hydrogenotrophic methanogen that possessed the two main complexes, methyl-CoM reductase (Mcr) and tetrahydromethanopterin-CoM methyltransferase (Mtr), the anaplerotic hydrogenases Eha and Ehb, and a set of other genes collectively called “methanogenesis markers” but could not oxidize alkanes. Overturning recent inferences, we demonstrate that methyl-dependent hydrogenotrophic methanogenesis has emerged multiple times independently, either due to a loss of Mtr while Mcr is inherited vertically or from an ancient lateral acquisition of Mcr. Even if Mcr is lost, Mtr, Eha, Ehb, and the markers can persist, resulting in mixotrophic metabolisms centered around the Wood-Ljungdahl pathway. Through their methanogenesis remnants, Thorarchaeia and two newly reconstructed order-level lineages in Archaeoglobi and Bathyarchaeia act as metabolically versatile players in carbon cycling of anoxic environments across the globe.