1. Large mammalian herbivores (LMH) exert strong effects on plants in tropical savannas, and many wild LMH populations are declining. However, predicting the impacts of these declines on vegetation structure remains challenging. 2. Experiments suggest that tree cover can increase rapidly following LMH exclusion. Yet it is unclear whether these results scale up to predict ecosystem-level impacts of LMH declines, which often alter fire regimes, trigger compensatory responses of other herbivores, and accompany anthropogenic land-use changes. Moreover, theory predicts that grazers and browsers should have opposing effects on tree cover, further complicating efforts to forecast the outcomes of community-wide declines. 3. We used the near-extirpation of grazing and browsing LMH from Gorongosa National Park during the Mozambican Civil War (1977-1992) as a natural experiment to test whether megafaunal collapse increased tree cover. We classified herbaceous and tree cover in satellite images taken (a) at the onset of war in 1977 and (b) in 2012, two decades after hostilities ceased. 4. Throughout the 3620-km2 park, proportional tree cover increased by 34% (from 0.29 to 0.39)—an addition of 362 km2. Four of the park's five major habitat zones (including miombo woodland, Acacia-Combretum-palm savanna, and floodplain grassland) showed even greater increases in tree cover (51–134%), with an average increase of 94% in ecologically critical Rift Valley habitats. Only in the eastern Cheringoma Plateau, which had historically low wildlife densities, did tree cover decrease (by 5%). 5. The most parsimonious explanation for these results is that reduced browsing pressure enhanced tree growth, survival, and/or recruitment; we found no directional trends in rainfall or fire that could explain increased tree cover. 6. Synthesis: Catastrophic large-herbivore die-offs in Mozambique's flagship national park were followed by 35 years of woodland expansion, most severely in areas where pre-war wildlife biomass was greatest. These findings suggest that browsing release supersedes grazer-grass-fire feedbacks in governing ecosystem-level tree cover, consistent with smaller-scale experimental results, although the potentially complementary effect of CO2 fertilization cannot be definitively ruled out. Future work in Gorongosa will reveal whether recovering LMH populations reverse this trend, or alternatively whether woody encroachment hinders ongoing restoration efforts.