Methanogenic Archaea play a key role in global methane cycling and represent the largest source of methane on Earth, hereby contributing to climate change. Although substantial insight has been gained into this unique group of microorganisms, our understanding of methanogenic diversity, metabolism and evolution is still incomplete. This is evidenced by the recent discovery of methane metabolism in members of the Bathyarchaeota, which challenges the traditional hypothesis that methanogenesis originated within the Euryarchaeota. Here we present the recovery of four population genomes (90-99% completeness) capable of methylotrophic methanogenesis belonging to two genera within a novel archaeal phylum, the Verstraetearchaeota. These microorganisms are found in anoxic environments with high methane flux including anaerobic digesters, formation waters, and tailings ponds. Their substrate profile and energy conservation mechanism most closely resemble the recently discovered obligate H2-dependent methylotrophic Methanomassiliicoccales and Candidatus ‘Methanofastidiosa’. Phylogenetic analysis of the methyl-coenzyme M reductase complex (MCR) allowed us to rule out recent lateral gene transfer from a euryarchaeotal donor to the Verstraetearchaeota. Our findings suggest that methanogenesis is more phylogenetically diverse than currently appreciated and that further divergent methanogenic lineages await discovery.