Thawing permafrost promotes microbial degradation of cryo-sequestered and new carbon leading to the biogenic production of methane, creating a positive feedback to climate change. Here we determine microbial community composition along a permafrost thaw gradient in northern Sweden. Partially thawed sites were frequently dominated by a single archaeal phylotype, Candidatus 'Methanoflorens stordalenmirensis' gen. nov. sp. nov., belonging to the uncultivated lineage 'Rice Cluster II' (Candidatus 'Methanoflorentaceae' fam. nov.). Metagenomic sequencing led to the recovery of its near-complete genome, revealing the genes necessary for hydrogenotrophic methanogenesis. These genes are highly expressed and methane carbon isotope data are consistent with hydrogenotrophic production of methane in the partially thawed site. In addition to permafrost wetlands, 'Methanoflorentaceae' are widespread in high methane-flux habitats suggesting that this lineage is both prevalent and a major contributor to global methane production. In thawing permafrost, Candidatus 'M. stordalenmirensis' appears to be a key mediator of methane-based positive feedback to climate warming.