Thermal-stress events are changing the composition of many coral reefs worldwide. Yet, determining the rates of coral recovery and their long-term responses to increasing sea-surface temperatures is challenging. To do so, we first estimated coral recovery rates following past disturbances on reefs in southern Japan and Western Australia. Recovery rates varied between regions, with the reefs in southern Japan showing more rapid recovery rates (intrinsic rate of increase, r = 0.38 year-1) than reefs in Western Australia (r = 0.17 year-1). Second, we input these recovery rates into a novel, nonlinear hybrid-stochastic-dynamical system to predict the responses of Indo-Pacific coral populations to complex inter-annual temperature cycles into the year 2100. The coral recovery rates were overlaid on background increases in global sea-surface temperatures, under three different climate-change scenarios. The models predicted rapid recovery at both localities with the infrequent and low-magnitude temperature anomalies expected under a conservative climate-change scenario, Representative Concentration Pathway (RCP) 4.5. With moderate increases in ocean temperatures (RCP 6.0) the coral populations showed a bimodal response, with model runs showing either recovery or collapse. Under a business-as-usual climate-change scenario (RCP 8.5), with frequent and intense temperature anomalies, coral recovery was unlikely.