Refuge availability and fishing alter predator-prey interactions on coral reefs, but our understanding of how they interact to drive food web dynamics, community structure and vulnerability of different trophic groups is unclear. Here, we apply a size-based ecosystem model of coral reefs, parameterized with empirical measures of structural complexity, to predict fish biomass, productivity and community structure in reef ecosystems under a broad range of refuge availability and fishing regimes. In unfished ecosystems, the expected positive correlation between reef structural complexity and biomass emerges, but a non-linear effect of predation refuges is observed for the productivity of predatory fish. Reefs with intermediate complexity have the highest predator productivity, but when refuge availability is high and prey are less available, predator growth rates decrease, with significant implications for fisheries. Specifically, as fishing intensity increases, predators in habitats with high refuge availability exhibit vulnerability to over-exploitation, resulting in communities dominated by herbivores. Our study reveals mechanisms for threshold dynamics in predators living in complex habitats and elucidates how predators can be food-limited when most of their prey are able to hide. We also highlight the importance of nutrient recycling via the detrital pathway, to support high predator biomasses on coral reefs.