With grasslands and savannas covering 20% of the world’s land surface, accounting for 30–35% of worldwide Net Primary Productivity and supporting hundreds of millions of people, predicting changes in tree/grass systems is priority. Inappropriate land management and rising atmospheric CO2 levels result in increased woody cover in savannas. Although woody encroachment occurs world-wide, Africa’s tourism and livestock grazing industries may be particularly vulnerable. Forecasts of responses of African wildlife and available grazing biomass to increases in woody cover are thus urgently needed. These predictions are hard to make due to non-linear responses and poorly understood feedback mechanisms between woody cover and other ecological responders, problems further amplified by the lack of long-term and large-scale datasets. We propose that a space-for-time analysis along an existing woody cover gradient overcomes some of these forecasting problems. Here we show, using an existing woody cover gradient (0–65%) across the Kruger National Park, South Africa, that increased woody cover is associated with (i) changed herbivore assemblage composition, (ii) reduced grass biomass, and (iii) reduced fire frequency. Furthermore, although increased woody cover is associated with reduced livestock production, we found indigenous herbivore biomass (excluding elephants) remains unchanged between 20–65% woody cover. This is due to a significant reorganization in the herbivore assemblage composition, mostly as a result of meso-grazers being substituted by browsers at increasing woody cover. Our results suggest that woody encroachment will have cascading consequences for Africa’s grazing systems, fire regimes and iconic wildlife. These effects will pose challenges and require adaptation of livelihoods and industries dependent on conditions currently prevailing.