For many species securing territories is important for feeding and reproduction. Factors such as competition, habitat availability, and male characteristics can influence an individual’s ability to establish and maintain a territory. The risk of predation can have an important influence on feeding and reproduction; however, few have studied its effect on territoriality. We investigated territoriality in a haremic, polygynous species of coral reef herbivore, Sparisoma aurofrenatum (redband parrotfish), across eight reefs in the Florida Keys National Marine Sanctuary that were either protected or unprotected from fishing of piscivorous fishes. We examined how territory size and quality varied with reef protection status, competition, predation risk, and male size. We then determined how territory size and quality influenced harem size and female size to understand the effect of territoriality on reproductive potential. We found that protected reefs trended towards having more large predatory fishes and that territories there were smaller but had greater algal nutritional quality relative to unprotected reefs. Our data suggest that even though males in protected sites have smaller territories, which support fewer females, they may improve their reproductive potential by choosing nutritionally rich areas, which support larger females. Thus, reef protection appears to shape the trade-off that herbivorous fishes make between territory size and quality. Furthermore, we provide evidence that males in unprotected sites, which are generally less complex than protected sites, choose territories with higher structural complexity, suggesting the importance of this type of habitat for feeding and reproduction in S. aurofrenatum. Our work argues that the loss of corals and the resulting decline in structural complexity, as well as management efforts to protect reefs, could alter the territory dynamics and reproductive potential of important herbivorous fish species.