Mediterranean phryganic ecosystems have been shaped for centuries by recurrent herbivory, yet the long-term ecological consequences of grazing cessation remain insufficiently resolved, particularly in protected island landscapes where conservation management often assumes that exclusion promotes recovery. In these drylands, the removal of grazing redirect assembly processes through shifts in dominance, heterogeneity, and functional strategy expression. Here, we use more than three decades-long grazing discontinuity within the Petrified Forest of Lesvos, an insular Mediterranean geopark, to examine how long-term herbivore exclusion reorganizes plant communities across taxonomic and functional dimensions. By integrating floristic inventories, multivariate community analysis, mixed-effects modeling, indicator species analysis, and community-weighted trait approaches, we reconstruct the ecological signature of grazing release in phryganic ecosystems. Long-term exclusion was associated with a broader species pool and a greater representation of protected taxa, while ungrazed communities exhibited lower Shannon and Simpson diversity, greater compositional dispersion, and a marked shift in dominance structure linked to the expansion of Sarcopoterium spinosum. Community differentiation was accompanied by directional reorganization of functional trait structure, with ungrazed plots characterized by taller vegetation and increased leaf and inflorescence length, indicating release from recurrent biomass removal and a transition toward more structurally expansive strategies. These results show that grazing exclusion does not simply enhance biodiversity, but reorganizes Mediterranean plant communities into an alternative ecological state shaped by altered competitive hierarchies, shrub-mediated filtering, and relaxed herbivory. In disturbance-structured island ecosystems, therefore, the ecological outcomes of protection depend not only on whether grazing is removed, but on how strongly community organization has historically depended on its continued presence.