Broad-scale phylogenetic studies give first insights in numbers, relationships, and ages of C4 lineages. They are, however, generally limited to a model that treats the evolution of the complex C4 syndrome in different lineages as a directly comparable process. Here, we use a resolved and well-sampled phylogenetic tree of Camphorosmeae, based on three chloroplast and one nuclear marker and on leaf anatomical traits to infer a more detailed picture of C4 leaf-type evolution in this lineage. Our ancestral character state reconstructions allowed two scenarios: (i) Sedobassia is a derived C3/C4 intermediate, implying two independent gains of C4 in Bassia and Camphorosma; or (ii) Sedobassia is a plesiomorphic C3/C4 intermediate, representing a syndrome ancestral to the Bassia/Camphorosma/Sedobassia lineage. In Bassia, a kochioid leaf type (Bassia muricata and/or Bassia prostrata type) is ancestral. At least three independent losses of water-storage tissue occurred, resulting in parallel shifts towards an atriplicoid leaf type. These changes in leaf anatomy are adaptations to different survival strategies in steppic or semi-desert habitats with seasonal rainfall. In contrast, Camphorosma shows a fixed C4 anatomy differing from Bassia types in its continuous Kranz layer, which indeed points to an independent origin of the full C4 syndrome in Camphorosma, either from an independent C3 or from a common C3/C4 intermediate ancestor, perhaps similar to its C3/C4 intermediate sister genus Sedobassia. The enlarged bundle sheath cells of Sedobassia might represent an important early step in C4 evolution in Camphorosmeae.