The genus Natronolimnobius, currently including four species, is a member of the order Natrialbales, class Halobacteria, and consists of obligately alkaliphilic and extremely halophilic members found exclusively in highly alkaline hypersaline soda lakes. The species were classified into this genus mostly based on phylogenetic analysis of the 16S rRNA gene. However, a more advanced phylogenomic reconstruction based on 122 conserved single-copy archaeal protein markers clearly indicates a polyphyletic origin of the species included into this genus, thus warranting its reclassification into three separate genera. We therefore propose to transfer Nlb. innermongolicus (type strain N-1311) to a new genus Natronolimnohabitans as Nlh. innermongolicus comb. nov. and to transfer Nlb. aegyptiacus (type strain JW/NM-HA 15) and Nlb. sulfurireducens (type strain AArc1) to a new genus Natrarchaeobaculum as Nbl. aegyptiacum comb. nov. and Nbl. sulfurireducens comb. nov. The phylogenomic differentiation of these four species is also supported by the ANI/AAI distances and unique phenotypes. The most important physiological differences includes a previously unreported ability for cellulose and xylan utilization in Nlb. baerhuensis, thermophily in Nbl. aegyptiacus and anaerobic sulfur respiration in Nbl. sulfurireducens. We further present an emended description of Natronolimnobius baerhuensis.