C4 photosynthesis is a complex trait that boosts productivity in tropical conditions. Compared with C3 species, the C4 state seems to require numerous novelties, but species comparisons can be confounded by long divergence times. Here, we exploit the photosynthetic diversity that exists within a single species, the grass Alloteropsis semialata, to detect changes in gene expression associated with different photosynthetic phenotypes. Phylogenetically informed comparative transcriptomics show that intermediates with a weak C4 cycle are separated from the C3 phenotype by increases in the expression of 58 genes (0.22% of genes expressed in the leaves), including those encoding just three core C4 enzymes: aspartate aminotransferase, phosphoenolpyruvate carboxykinase, and phosphoenolpyruvate carboxylase. The subsequent transition to full C4 physiology was accompanied by increases in another 15 genes (0.06%), including only the core C4 enzyme pyruvate orthophosphate dikinase. These changes probably created a rudimentary C4 physiology, and isolated populations subsequently improved this emerging C4 physiology, resulting in a patchwork of expression for some C4 accessory genes. Our work shows how C4 assembly in A. semialata happened in incremental steps, each requiring few alterations over the previous step. These create short bridges across adaptive landscapes that probably facilitated the recurrent origins of C4 photosynthesis through a gradual process of evolution.