Abstract The Chenopodiaceae includes taxa with both C3 and C4 photosynthesis with diverse kinds of Kranz anatomy and single-celled C4 species without Kranz anatomy; thus, it is of key importance for understanding evolution of C4 photosynthesis. All of the C4 genera except Atriplex, which belongs to Chenopodioideae, are in the Salicornioideae / Suaedoideae / Salsoloideae s.l. (including Camphorosmeae and Sclerolaeneae) clade. Our study focused on the relationships of the main lineages within this clade with an emphasis on the placement of the single cell functioning C4 genus Bienertia using maximum parsimony, maximum likelihood, and Bayesian inference phylogenetic analyses of the nuclear ribosomal ITS and five chloroplast DNA regions (atpB-rbcL, matK, psbB-psbH, rbcL, and trnL-trnF). Further we provide a detailed phylogeny of Alexandra and Suaeda based on ITS, atpB-rbcL, and psbB-psbH. Our molecular data provide strong statistical support for the monophyly of: (1) a Salicornioideae / Suaedoideae / Salsoloideae s.l. clade; (2) a Salicornioideae / Suaedoideae clade; (3) the subfamilies Salicornioideae, Suaedoideae (including Bienertia) and Salsoloideae s.l.; (4) the tribes Suaedeae, Salsoleae, and Camphorosmeae; (5) the Salicornieae if Halopeplideae is included; and (6) Suaeda if Alexandra is included. Alexandra lehmannii is therefore reclassified as Suaeda lehmannii and a new section of Suaeda is created, section Alexandra. There are four independent origins of C4 photosynthesis within the Suaedoideae including two parallel origins of Kranz C4 anatomy (in Suaeda sections Salsina s.l. and Schoberia) and two independent origins of C4 systems without Kranz anatomy (in Bienertia and in Suaeda section Borszczowia).