Phylogenetic relationships within the halophilic archaea were inferred from comparisons of the 16S rRNA gene sequences from 61 strains, representing 18 genera with validly published names within the order Halobacteriales. Trees produced using distance-matrix (least-squares and neighbour-joining) methods affirm with strong bootstrap support that the members of the order Halobacteriales are a monophyletic group. Ten genera were supported as monophyletic groups [Haloarcula, Halobiforma, Halococcus, Haloferax, Halorubrum, Halosimplex (multiple sequences from a single strain), Natrialba, Natrinema, Natronococcus and Natronorubrum] and eight genera were represented by a single strain (Halobacterium, Halobaculum, Halogeometricum, Halomicrobium, Halorhabdus, Halosimplex, Natronobacterium and Natronomonas). The genus Haloterrigena was always paraphyletic, and the phylogenetic placement of and sister groups to Halobacterium and Natronomonas could not be resolved. Both treeing methods failed to resolve the deep branching patterns within the order Halobacteriales and the relationships between the major clades. Additional representation from the currently monospecific genera and/or the use of other macromolecules may be required to resolve the relationships within the order Halobacteriales.