Historical exploitation of the Mediterranean Sea and the absence of rigorous baselines makes it difficult to evaluate the current health of the marine ecosystems and the efficacy of conservation actions at the ecosystem level. Here we establish the first current baseline and gradient of ecosystem structure of nearshore rocky reefs at the Mediterranean scale. We conducted underwater surveys in 14 marine protected areas and 18 open access sites across the Mediterranean, and across a 31-fold range of fish biomass (from 3.8 to 118 g m-2). Our data showed remarkable variation in the structure of rocky reef ecosystems. Multivariate analysis showed three alternative community states: (1) large fish biomass and reefs dominated by non-canopy algae, (2) lower fish biomass but abundant native algal canopies and suspension feeders, and (3) low fish biomass and extensive barrens, with areas covered by turf algae. Our results suggest that the healthiest shallow rocky reef ecosystems in the Mediterranean have both large fish and algal biomass. Protection level and primary production were the only variables significantly correlated to community biomass structure. Fish biomass was significantly larger in well-enforced no-take marine reserves, but there were no significant differences between multi-use marine protected areas (which allow some fishing) and open access areas at the regional scale. The gradients reported here represent a trajectory of degradation that can be used to assess the health of any similar habitat in the Mediterranean, and to evaluate the efficacy of marine protected areas.