Halophilic methanogens play an important role in the carbon cycle in hypersaline environments, but are under-represented in culture collections. In this study, we describe a novel Methanohalophilus strain that was isolated from the sulfide-rich brine-seawater interface of Kebrit Deep in the Red Sea. Based on physiological and phylogenomic features, strain RSK, which is the first methanogenic archaeon to be isolated from a deep hypersaline anoxic brine lake of the Red Sea, represents a novel species of this genus. In order to compare the genetic traits underpinning the adaptations of this genus in diverse hypersaline environments, we sequenced the genome of strain RSK and compared it with genomes of previously isolated and well characterized species in this genus (Methanohalophilus mahii, Methanohalophilus halophilus, Methanohalophilus portucalensis, and Methanohalophilus euhalobius). These analyses revealed a highly conserved genomic core of greater than 93% of annotated genes (1490 genes) containing pathways for methylotrophic methanogenesis, osmoprotection through salt-out strategy, and oxidative stress response, among others. Despite the high degree of genomic conservation, species-specific differences in sulfur and glycogen metabolisms, viral resistance, amino acid, and peptide uptake machineries were also evident. Thus, while Methanohalophilus species are found in diverse extreme environments, each genotype also possesses adaptive traits that are likely relevant in their respective hypersaline habitats.