Fishing has clear direct effects on harvested species, but its cascading, indirect effects are less well understood. Fishing disproportionately removes larger, predatory fishes from marine food webs. Most studies of the consequent indirect effects focus on density-mediated interactions where predator removal alternately drives increases and decreases in abundances of successively lower trophic-level species. While prey may increase in number with fewer predators, they may also alter their behavior. When such behavioral responses impact the food resources of prey species, behaviorally mediated trophic cascades can dramatically shape landscapes. It remains unclear whether this pathway of change is typically triggered by ocean fishing. By coupling a simple foraging model with empirical observations from coral reefs, we provide a mechanistic basis for understanding and predicting how predator harvest can alter the landscape of risk for herbivores and consequently drive dramatic changes in primary producer distributions. These results broaden trophic cascade predictions for fisheries to include behavioral changes. They also provide a framework for detecting the presence and magnitude of behaviorally mediated cascades. This knowledge will help to reconcile the disparity between expected and observed patterns of fishing-induced cascades in the sea.