Unsustainable grazing is a major driver of biodiversity loss worldwide. Conservation actions such as grazing exclusion are effective strategies for halting such decline. However, we still know little how the long-term impact of grazing exclusion depends on plant–animal interactions such as those between encroaching unpalatable shrubs and ground arthropods. Here, we assessed how encroaching, unpalatable shrub species (Sarcopoterium spinosum) mediates the effects of grazing exclusion on the recovery of arthropod communities. We used a large-scale, long-term (15–25 years) grazing exclusion experiment complemented with local-scale treatments that consider the presence or absence of shrubs. We found that halting overgrazing supported the recovery of biodiversity in the long-term. Notably, the impacts of shrubs on arthropod diversity vary with grazing history. Shrubs decreased arthropod abundance by three folds, affecting particularly flies, butterflies, hymenopteran, and beetles in protected areas. Yet, shrubs had positive effects on animal diversity, particularly centipedes and millipeds in grazed areas. On the one hand, shrubs may enhance biodiversity recovery in overgrazed systems; on the other hand, shrubs may be detrimental in protected areas, in the absence of grazing. Understanding how plant–animal interactions vary with historical land-use change is key for biodiversity conservation and recovery and for integrated management of agroecosystems.