Trophic rewilding seeks to rehabilitate degraded ecosystems by repopulating them with large animals, thereby re-establishing strong top-down interactions. Yet there are very few tests of whether such initiatives can restore ecosystem structure and functions, and on what timescales. Here we show that war-induced collapse of large-mammal populations in Mozambique's Gorongosa National Park exacerbated woody encroachment by the invasive shrub Mimosa pigra-considered one of the world's 100 worst invasive species-and that one decade of concerted trophic rewilding restored this invasion to pre-war baseline levels. Mimosa occurrence increased between 1972 and 2015, a period encompassing the near extirpation of large herbivores during the Mozambican Civil War. From 2015 to 2019, mimosa abundance declined as ungulate biomass recovered. DNA metabarcoding revealed that ruminant herbivores fed heavily on mimosa, and experimental exclosures confirmed the causal role of mammalian herbivory in containing shrub encroachment. Our results provide mechanistic evidence that trophic rewilding has rapidly revived a key ecosystem function (biotic resistance to a notorious woody invader), underscoring the potential for restoring ecological health in degraded protected areas.