Interest and controversy surrounding the evolutionary origins of extremely halophilic Archaea has increased in recent years, due to the discovery and characterization of the Nanohaloarchaea and the Methanonatronarchaeia. Initial attempts in explaining the evolutionary placement of the two new lineages in relation to the classical Halobacteria (also referred to as Haloarchaea) resulted in hypotheses that imply the new groups share a common ancestor with the Haloarchaea. However, more recent analyses have led to a shift: the Nanohaloarchaea have been largely accepted as being a member of the DPANN superphylum, outside of the euryarchaeota; while the Methanonatronarchaeia have been placed near the base of the Methanotecta (composed of the class II methanogens, the halobacteriales, and archaeoglobales). These opposing hypotheses have far-reaching implications on the concepts of convergent evolution (unrelated groups evolve similar strategies for survival), genome reduction, and gene transfer. In this work, we attempt to resolve these conflicts with phylogenetic and phylogenomic data. We provide a robust taxonomic sampling of Archaeal genomes that spans the crenarchaeota, euryarchaeota, and the DPANN superphylum. In addition, we sampled and assembled 7 new representatives of the Nanohaloarchaea, from distinct geographic locations. Phylogenies derived from these data imply the highly conserved ATP synthase catalytic/non-catalytic subunits of Nanohaloarchaea share a sisterhood relationship with the Haloarchaea. This relationship, with strong support, was also observed for several other gene families. In addition, we present and evaluate data that argue for and against the monophyly of the DPANN superphylum. We employed phylogenetic reconstruction, constrained topology tests, and gene concordance factors to explore the support for and against the monophyly of the Haloarchaea, Nanohaloarchaea, and Methanonatronarchaeia.