In grasses, almost all species belong to two evenly sized clades (BOP and PACMAD), yet the >20 independent origins of C₄ photosynthesis in this family only occur in the PACMAD lineage. Here, we identify potential genetic precursors for C₄ photosynthesis that were present at the base of the PACMAD clade, representing the last common ancestor of all C₄ grasses. We generated the first reference genomes for Aristidoideae species (Aristida adscensionis and Stipagrostis hirtigluma), the sister lineage of all other PACMAD grasses. In combination with 34 other Poales genomes, we identify gene gains at the base of the PACMAD clade, and genes lost in the sister BOP lineage. Candidate C₄ precursors include β-carbonic anhydrase, as well as genes involved in amino acid and nitrate transport, carbon metabolism, oxidative stress management and transcription regulation. Gene turnover created the necessary genetic contingency, facilitating the independent recruitment and refinement of C₄ genes in multiple independent origins. Our results support the idea that the repeated evolution of C₄ photosynthesis in PACMAD grasses was not driven by a single genetic event but was instead underwritten by chance genetic changes that originated long before there was selection for the trait itself.