Fishes of the genus Gobiodon are habitat specialists by their association with Acropora corals. Little is known about the parameters that define host coral quality for these fishes, in particular their breeding pairs. Data were collected in the northern Red Sea using 10 9 1-m belt transects in different reefs and zones. Gobiid density was highly correlated with coral density over all sites and zones, and the more specialized goby species preferred coral species that are less vulnerable to environmental stress. Moreover, the occupation rate of corals by goby breeding pairs significantly increased with colony size and decreased with partial mortality of colonies. Logistic regression showed that both coral size (being most important) and partial mortality are key factors influencing the occupation by breeding pairs. This study provides the first evidence that breeding pairs of coral-associated gobiids have more advanced habitat requirements than conspecifics in other social states. As coral reefs are threatened worldwide and habitat loss and degradation increase, this information will help predict the potential effects on those reef fishes obligatorily associated with live corals.