The dynamic nature of coral reefs offers a rare opportunity to examine the response of ecosystems to disruption due to climate change. In 1998, the Great Barrier Reef experienced widespread coral bleaching and mortality. As a result, cryptobenthic fish assemblages underwent a dramatic phase-shift. Thirteen years, and up to 96 fish generations later, the cryptobenthic fish assemblage has not returned to its pre-bleach configuration. This is despite coral abundances returning to, or exceeding, pre-bleach values. The post-bleach fish assemblage exhibits no evidence of recovery. If these short-lived fish species are a model for their longer-lived counterparts, they suggest that (1) the full effects of the 1998 bleaching event on long-lived fish populations have yet to be seen, (2) it may take decades, or more, before recovery or regeneration of these long-lived species will begin, and (3) fish assemblages may not recover to their previous composition despite the return of corals.