CAM and C4 photosynthesis are two key plant adaptations that have evolved independently multiple times, and are especially prevalent in particular groups of plants, including the Caryophyllales. We investigate the origin of photosynthetic PEPC, a key enzyme of both the CAM and C4 pathways. We combine phylogenetic analyses of genes encoding PEPC with analyses of RNA sequence data of Portulaca, the only plants known to perform both CAM and C4 photosynthesis. Three distinct gene lineages encoding PEPC exist in eudicots (namely ppc-1E1, ppc-1E2 and ppc-2), one of which (ppc-1E1) was recurrently recruited for use in both CAM and C4 photosynthesis within the Caryophyllales. This gene is present in multiple copies in the cacti and relatives, including Portulaca. The PEPC involved in the CAM and C 4 cycles of Portulaca are encoded by closely related yet distinct genes. The CAM-specific gene is similar to genes from related CAM taxa, suggesting that CAM has evolved before C4 in these species. The similar origin of PEPC and other genes involved in the CAM and C4 cycles highlights the shared early steps of evolutionary trajectories towards CAM and C4, which probably diverged irreversibly only during the optimization of CAM and C4 phenotypes.