Repeated bouts of coral bleaching threaten the long-term persistence of coral reefs and associated communities. Here, we document the short- and long-term impacts of heatwave events on coral and fish assemblages, based on regular surveys of 18 reefs of the granitic islands of Seychelles over 23 yr. Extreme heat events in 1998 and 2016 led to bleaching-associated declines in coral cover, whilst between these years there was an interim period of coral recovery on some reefs. Coral decline and recovery were primarily due to changes in the cover of branching coral, particularly those from the families Acroporidae and Pocilloporidae. Surveys during the 2016 bleaching found that 95% of the 468 Acropora and Pocillopora colonies observed were either bleached or recently dead. The extent of bleaching and subsequent mortality were best explained by a priori assessments of community susceptibility to heat stress. One year later (2017), coral cover had fallen by 70% and average coverage across the 18 reefs was at 6%, similar to levels recorded in 2005, 7 yr after the 1998 bleaching. Decline in coral following the 2016 bleaching coincided with reduced abundance of fish < 11 cm TL, particularly corallivores, invertivores and mixed diet feeders. These changes are likely to foreshadow more widespread loss once the habitat structure erodes. Accordingly, 7 yr after the 1998 bleaching, when coral skeletons and reef structure had collapsed on some reefs, abundance of both large- and small-bodied fish had declined. We show that fluctuation in the cover of branching coral is positively associated with changes in the abundance of small-bodied fish which contribute to ecological processes and high diversity, suggesting branching corals are a keystone structure. Increased frequency of bleaching threatens the capacity of branching corals to fully recover after disturbances, reducing the amplitude of boom bust cycles of these corals and the keystone habitat structure they provide reef fish.