Understanding the roles of top-down and bottom-up forces in determining community structure and resilience has increasingly become the focus of ecological studies as human influences on ecosystems have intensified, changing the strength of forces, and resulting in phase shifts to alternate states. Recent phase shifts of marine communities are attributed to human impacts, including nutrient enrichment, overfishing of predatory and herbivorous fishes, and increases in environmental stress. For coral reefs, many have hypothesized that herbivores are of primary importance to reef resilience, limiting the proliferation of macroalgae and enhancing coral recovery after stress. However, there have been no experimental studies testing this hypothesis. Here we provide evidence that an intact herbivore community reversed macroalgal overgrowth of coral following a period of environmental stress. Recovery of coral dominance after episodic low-temperature stress was dependent upon the presence of herbivores, a top-down force that removed algal proliferation and prevented further coral mortality. Without environmental stress, no phase shift was initiated indicating that reductions in herbivory alone may not cause community shifts. Rather, without environmental stress both herbivory and bottom-up forcing by nutrients regulated coral/algal dominance, although the magnitude of community changes was relatively modest. We conclude that the ability of coral communities to recover from environmental stress is undermined by overfishing, while maintenance of reef stability is also dependent on nutrients. Our results provide scientific support for the worldwide call for protection of reef fishes as a key management goal, especially in the face of increasing nutrification and environmental stress.