The Salicornioideae Kostel. are distinctive among the Chenopodiaceae Venet.. However, their phylogenetic relationships are poorly understood. Analyses of morphological and molecular characters were undertaken to evaluate relationships within the subfamily and to test the monophyly of the endemic Australian genera Halosarcia Paul G. Wilson, Pachycornia Hook.f., Sclerostegia Paul G. Wilson, Tecticornia Hook.f. and Tegicornia Paul G. Wilson. Kalidium Moq. and Halopeplis Bunge ex Ung.-Sternb. of the tribe Halopeplideae were used as outgroup representatives in the morphological analysis and resolved sister to the tribe Salicornieae. Allenrolfea Kuntze; Halocnemum Bieb. and Heterostachys Meyer formed an early branching group sister to a moderately supported clade comprised of the remaining Salicornieae. Only terminal groups of closely related species received significant bootstrap support in this analysis. In contrast, the current tribal classification of the Salicornioideae was not supported in the molecular analysis as Allenrolfea occidentalis Kuntz (tribe Salicornieae) positioned sister to Kalidium foliatum Moq. (tribe Halopeplideae) and the remaining Salicornieae. Three major clades received strong bootstrap support: Microcnemum+Arthrocnemum, Sarcocornia+Salicornia, and the endemic Australian genera. None of the endemic Australian genera was individually supported as monophyletic in either the morphological or the molecular analyses. Subspecies complexes, polyploids and hybrids may contribute to the lack of resolution and apparently high levels of homoplasy in the morphological analysis. A greater understanding of population level processes is required to begin to resolve the phylogeny of this complex group.