Livestock overgrazing causes environmental degradation, species invasion, biodiversity loss, and productivity decline, with profound consequences for ecological sustainability and human livelihoods. Habitat protection can mitigate such impacts, but we know little about how the long-term recovery of plant communities from livestock overgrazing depends on the presence of encroaching shrubs. Here, we explored how shrub encroachment mediates the effects of habitat protection (i.e., livestock exclusion and creation of UNESCO protected areas) on biodiversity recovery and ecosystem functioning (i.e., biomass productivity). We leveraged a long-term (15–25 years) experiment of livestock exclusion and complemented it with the removal of an encroaching shrub species in pasture areas and protected areas. We reveal that habitat protection has positive effects on patterns of recovery. Yet, the effects of habitat protection are mediated by shrub encroachment. Encroaching shrubs have net positive effects on plant diversity in pasture areas but inhibit biodiversity recovery in protected areas. The combination of habitat protection and the removal of encroaching shrubs best enhances the recovery of plant diversity and biomass productivity. A potential underlying mechanism is the shift in plant interactions from facilitation for recruitment and associated resistance to competition for water. Understanding species interactions is key to guiding conservation and restoration actions which can turn degraded ecosystems back into functional, species-rich communities.