Recent episodes of coral bleaching have led to wide-scale loss of reef corals and raised concerns over the effectiveness of existing conservation and management efforts. The 1998 bleaching event was most severe in the western Indian Ocean, where coral declined by up to 90% in some locations. Using fisheries-independent data, we assessed the long-term impacts of this event on fishery target species in the Seychelles, the overall size structure of the fish assemblage, and the effectiveness of two marine protected areas (MPAs) in protecting fish communities. The biomass of fished species above the size retained in fish traps changed little between 1994 and 2005, indicating no current effect on fishery yields. Biomass remained higher in MPAs, indicating they were effective in protecting fish stocks. Nevertheless, the size structure of the fish communities, as described with size-spectra analysis, changed in both fished areas and MPAs, with a decline in smaller fish (<30 cm) and an increase in larger fish (>45 cm). We believe this represents a time-lag response to a reduction in reef structural complexity brought about because fishes are being lost through natural mortality and fishing, and are not being replaced by juveniles. This effect is expected to be greater in terms of fisheries productivity and, because congruent patterns are observed for herbivores, suggests that MPAs do not offer coral reefs long-term resilience to bleaching events. Corallivores and planktivores declined strikingly in abundance, particularly in MPAs, and this decline was associated with a similar pattern of decline in their preferred corals. We suggest that climate-mediated disturbances, such as coral bleaching, be at the fore of conservation planning for coral reefs.