Global climate change is rapidly altering disturbance regimes in many ecosystems including coral reefs, yet the long-term impacts of these changes on ecosystem structure and function are difficult to predict. A major ecosystem service provided by coral reefs is the provisioning of physical habitat for other organisms, and consequently, many of the effects of climate change on coral reefs will be mediated by their impacts on habitat structure. Therefore, there is urgent need to understand the independent and combined effects of coral mortality and loss of physical habitat on reef-associated biota. Here, we use a unique series of events affecting the coral reefs around the Pacific island of Moorea, French Polynesia to differentiate between the impacts of coral mortality and the degradation of physical habitat on the structure of reef fish communities. We found that by removing large amounts of physical habitat, a tropical cyclone had larger impacts on reef fish communities than an outbreak of coral-eating sea stars that caused widespread coral mortality but left the physical structure intact. In addition, the impacts of declining structural complexity on reef fish assemblages accelerated as structure became increasingly rare. Structure provided by dead coral colonies can take up to decades to erode following coral mortality, and consequently our results suggest that predictions based on short-term studies are likely to grossly underestimate the long-term impacts of coral decline on reef fish communities.