C4 plants are widely successful in the grass-dominated ecosystems of tropical, subtropical, and warm-temperate regions, largely as a result of their ability to limit photorespiration and improve water-use efficiency. A widely held paradigm is that low (<∼400 ppm) atmospheric CO2 concentrations were an important factor selecting for the origin of C4 plants, although support in geological records is limited. We determined the carbon isotopic composition of 686 individual grass-pollen grains preserved in eight samples of lacustrine and shallow-marine sediments from three basins spanning the Early Oligocene to Middle Miocene in southwestern Europe. Grasses composed <15% of the total abundance of terrestrial pollen grains, and 26%–62% of the grass pollen was from C4 grasses. Thus C4 grasses occurred on the landscape as early as the earliest Oligocene, ∼14 m.y. earlier than previous isotopic evidence of first C4 plants and before pCO2 fell during the Oligocene.