The dominant forcing factors for past large-scale changes in vegetation are widely debated. Changes in the distribution of C4 plants--adapted to warm, dry conditions and low atmospheric CO2 concentrations--have been attributed to marked changes in environmental conditions, but the relative impacts of changes in aridity, temperature and CO2 concentration are not well understood. Here, we present a record of African C4 plant abundance between 1.2 and 0.45 million years ago, derived from compound-specific carbon isotope analyses of wind-transported terrigenous plant waxes. We find that large-scale changes in African vegetation are linked closely to sea surface temperatures in the tropical Atlantic Ocean. We conclude that, in the mid-Pleistocene, changes in atmospheric moisture content--driven by tropical sea surface temperature changes and the strength of the African monsoon--controlled aridity on the African continent, and hence large-scale vegetation changes.