The haloarchaeal genera Natrinema and Haloterrigena were described almost simultaneously by two different research groups and some strains studied separately were described as different species of these genera. Furthermore, the description of additional species were assigned to either Natrinema or Haloterrigena, mainly on the basis of the phylogenetic comparative analysis of single genes (16S rRNA gene and more recently rpoB’ gene), but these species were not adequately separated or assigned to the corresponding genus. Some studies suggested that the species of these two genera should be unified into a single genus, while other studies indicated that the genera should remain but some of the species should be reassigned. In this study, we have sequenced or collected the genomes of the type strains of species of Natrinema and Haloterrigena and we have carried out a comparative genomic analysis in order to clarify the controversy related to these two genera. The phylogenomic analysis based on the comparison of 525 translated single-copy orthologous genes and the Overall Genome Relatedness Indexes (i.e., AAI, POCP, ANI, and dDDH) clearly indicate that the species Haloterrigena hispanica, Haloterrigena limicola, Haloterrigena longa, Haloterrigena mahii, Haloterrigena saccharevitans, Haloterrigena thermotolerans, and Halopiger salifodinae should be transferred to the genus Natrinema, as Natrinema hispanicum, Natrinema limicola, Natrinema longum, Natrinema mahii, Natrinema saccharevitans, Natrinema thermotolerans, and Natrinema salifodinae, respectively. On the contrary, the species Haloterrigena turkmenica, Haloterrigena salifodinae, and Haloterrigena salina will remain as the only representative species of the genus Haloterrigena. Besides, the species Haloterrigena daqingensis should be reclassified as a member of the genus Natronorubrum, as Natronorubrum daqingense. At the species level, Haloterrigena jeotgali and Natrinema ejinorense should be considered as a later heterotypic synonyms of the species Haloterrigena (Natrinema) thermotolerans and Haloterrigena (Natrinema) longa, respectively. Synteny analysis and phenotypic features also supported those proposals.