Ecological communities are reorganizing in response to warming temperatures. For continuous ocean habitats this reorganization is characterized by large-scale species redistribution, but for tropical discontinuous habitats such as coral reefs, spatial isolation coupled with strong habitat dependence of fish species imply that turnover and local extinctions are more significant mechanisms. In these systems, transient marine heatwaves are causing coral bleaching and profoundly altering habitat structure, yet despite severe bleaching events becoming more frequent and projections indicating annual severe bleaching by the 2050s at most reefs, long-term effects on the diversity and structure of fish assemblages remain unclear. Using a 23-year time series spanning a thermal stress event, we describe and model structural changes and recovery trajectories of fish communities after mass bleaching. Communities changed fundamentally, with the new emergent communities dominated by herbivores and persisting for >15 years, a period exceeding realized and projected intervals between thermal stress events on coral reefs. Reefs which shifted to macroalgal states had the lowest species richness and highest compositional dissimilarity, whereas reefs where live coral recovered exceeded prebleaching fish richness, but remained dissimilar to prebleaching compositions. Given realized and projected frequencies of bleaching events, our results show that fish communities historically associated with coral reefs will not re-establish, requiring substantial adaptation by managers and resource users.