To reconstruct phylogeny and verify the monophyly of major subgroups, a total of 52 species representing almost all species of Salsoleae s.l. in China were sampled, with analysis based on three molecular markers (nrDNA ITS, cpDNA psbB–psbH and rbcL), using maximum parsimony, maximum likelihood, and Bayesian inference methods. Our molecular evidence provides strong support for the following: (1) Camphorosmeae is nested within Salsoleae s.l. instead of the previously suggested sister relationship. (2) Tribe Salsoleae s.l. is monophyletic and is composed of three monophyletic subunits, Caroxyloneae, the Kali clade, and Salsoleae s.str. (3) Climacoptera is separated from Salsola s.l. It does not form a monophyletic group but is split into two monophyletic parts, Climacoptera I and Climacoptera II. (4) Halogeton is clearly polyphyletic, as are Anabasis and the genus Salsola s.l. (5) Caroxylon, Haloxylon, Kali, and Petrosimonia are well-supported monophyletic genera. Additional evidence is needed regarding the monophyly of Halimocnemis, which remains unclear.