C4 photosynthesis evolved over 65 times, with around 24 origins in the eudicot order Caryophyllales. In the Caryophyllales family Nyctaginaceae, the C4 pathway is known in three genera of the tribe Nyctagineae: Allionia, Okenia and Boerhavia. Phylogenetically, Allionia and Boerhavia/Okenia are separated by three genera whose photosynthetic pathway is uncertain. To clarify the distribution of photosynthetic pathways in the Nyctaginaceae, we surveyed carbon isotope ratios of 159 species of the Nyctaginaceae, along with bundle sheath (BS) cell ultrastructure, leaf gas exchange, and C4 pathway biochemistry in five species from the two C4 clades and closely related C3 genera. All species in Allionia, Okenia and Boerhavia are C4, while no C4 species occur in any other genera of the family, including three that branch between Allionia and Boerhavia. This demonstrates that C4 photosynthesis evolved twice in Nyctaginaceae. Boerhavia species use the NADP-malic enzyme (NADP-ME) subtype of C4 photosynthesis, while Allionia species use the NAD-malic enzyme (NAD-ME) subtype. The BS cells of Allionia have many more mitochondria than the BS of Boerhavia. Bundle sheath mitochondria are closely associated with chloroplasts in Allionia which facilitates CO2 refixation following decarboxylation by mitochondrial NAD-ME. The close relationship between Allionia and Boerhavia could provide insights into why NADP-ME versus NAD-ME subtypes evolve, particularly when coupled to analysis of their respective genomes. As such, the group is an excellent system to dissect the organizational hierarchy of convergent versus divergent traits produced by C4 evolution, enabling us to understand when convergence is favored versus when divergent modifications can result in a common phenotype.