Methanogenic archaea are major players in the global carbon cycle and in the biotechnology of anaerobic digestion. The phylum Euryarchaeota includes diverse groups of methanogens that are interspersed with non-methanogenic lineages. So far, methanogens inhabiting hypersaline environments have been identified only within the order Methanosarcinales. We report the discovery of a deep phylogenetic lineage of extremophilic methanogens in hypersaline lakes and present analysis of two nearly complete genomes from this group. Within the phylum Euryarchaeota, these isolates form a separate, class-level lineage 'Methanonatronarchaeia' that is most closely related to the class Halobacteria. Similar to the Halobacteria, 'Methanonatronarchaeia' are extremely halophilic and do not accumulate organic osmoprotectants. The high intracellular concentration of potassium implies that 'Methanonatronarchaeia' employ the 'salt-in' osmoprotection strategy. These methanogens are heterotrophic methyl-reducers that use C-1-methylated compounds as electron acceptors and formate or hydrogen as electron donors. The genomes contain an incomplete and apparently inactivated set of genes encoding the upper branch of methyl group oxidation to CO2 as well as membrane-bound heterodisulfide reductase and cytochromes. These features differentiate 'Methanonatronarchaeia' from all known methyl-reducing methanogens. The discovery of extremely halophilic, methyl-reducing methanogens related to haloarchaea provides insights into the origin of methanogenesis and shows that the strategies employed by methanogens to thrive in salt-saturating conditions are not limited to the classical methylotrophic pathway.