Climate-induced coral bleaching is among the greatest current threats to coral reefs, causing widespread loss of live coral cover1. Conditions under which reefs bounce back from bleaching events or shift from coral to algal dominance are unknown, making it difficult to predict and plan for differing reef responses under climate change2. Here we document and predict long-term reef responses to a major climate-induced coral bleaching event that caused unprecedented region-wide mortality of Indo-Pacific corals. Following loss of >90% live coral cover, 12 of 21 reefs recovered towards pre-disturbance live coral states, while nine reefs underwent regime shifts to fleshy macroalgae. Functional diversity of associated reef fish communities shifted substantially following bleaching, returning towards pre-disturbance structure on recovering reefs, while becoming progressively altered on regime shifting reefs. We identified threshold values for a range of factors that accurately predicted ecosystem response to the bleaching event. Recovery was favoured when reefs were structurally complex and in deeper water, when density of juvenile corals and herbivorous fishes was relatively high and when nutrient loads were low. Whether reefs were inside no-take marine reserves had no bearing on ecosystem trajectory. Although conditions governing regime shift or recovery dynamics were diverse, pre-disturbance quantification of simple factors such as structural complexity and water depth accurately predicted ecosystem trajectories. These findings foreshadow the likely divergent but predictable outcomes for reef ecosystems in response to climate change, thus guiding improved management and adaptation.