Microbial methanogenesis may have been a major component of Earth’s carbon cycle during the Archaean eon, generating a methane greenhouse that increased global temperatures enough for a liquid hydrosphere, despite the Sun’s lower luminosity at the time. Evaluation of potential solutions to the ‘faint young Sun’ hypothesis by determining the age of microbial methanogenesis has been limited by ambiguous geochemical evidence and the absence of a diagnostic fossil record. To overcome these challenges, we use a temporal constraint: a horizontal gene transfer event from within archaeal methanogens to the ancestor of Cyanobacteria, one of the few microbial clades with recognized crown-group fossils. Results of molecular clock analyses calibrated by this horizontal-gene-transfer-propagated constraint show methanogens diverging within Euryarchaeota no later than 3.51 billion years ago, with methanogenesis itself probably evolving earlier. This timing provides independent support for scenarios wherein microbial methane production was important in maintaining temperatures on the early Earth.