C4 photosynthesis is a complex trait that boosts productivity in tropical conditions. Compared to 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: ASP-AT, PCK, and PEPC. The subsequent transition to full C4 physiology was accompanied by increases in another 15 genes (0.06%), including only the core C4 enzyme PPDK. These changes likely 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 one. These create short bridges across adaptive landscapes that likely facilitated the recurrent origins of C4 photosynthesis through a gradual process of evolution.