Herbivorous fish play a key role in the resilience of coral reefs to climatic stressors. In the Egyptian Gulf of Aqaba (GoA), many of these herbivores are important targets for artisanal fishing. Moreover, little is known about the status of their biomass and size-structure patterns. Therefore, this study was conducted to investigate the status of herbivorous fish communities at 30 reef sites in eight regions at the western side of the GoA. Notably, these regions are subject to three levels of fishing and protection, ranging from almost unfished (no-take, NT) to moderately fished (gear-restriction, GR) or heavily fished (open-access, OA). The results of this study showed that no-take fishery reserves are the most effective in maintaining the richness, body size, and biomass of all functional groups of herbivorous fishes. Total herbivorous fish biomass was 4.3 and 2.8 times higher on NT reefs and GR reefs, respectively than on OA reefs. Among GoA regions, only Ras Mohammed and Sharm El-Sheikh (unfished) and Nabq (moderately fished) met the global mean herbivorous fish biomass target of 30 kg/500 m². The current work highlighted three important results: (i) size structure of herbivorous fishes was heavily skewed toward smaller individuals, with fishes less than 20 cm accounting for 81.1% of the population at OA (heavily fished) reefs vs. 52.8% at NT (unfished) reefs; (ii) biomass of larger herbivore individuals (> 35 cm) accounted for less than 1% of the total biomass in OA reefs vs. 37% at NT reefs; (iii) large-bodied target species, such as Cetoscarus bicolor, Naso unicorn, and Kyphosus spp., accounted for 15.9% of the total biomass at NT reefs, while they were virtually absent from OA reefs. Collectively, these findings suggest that many principal fishery species in the northern regions of the GoA have been overfished, which in turn can lead to coral reef degradation.