The long-term response of coral reefs to climate change depends on the ability of reef-building coral symbioses to adapt or acclimatize to warmer temperatures, but there has been no direct evidence that such a response can occur. Here we show that corals containing unusual algal symbionts that are thermally tolerant and commonly associated with high-temperature environments are much more abundant on reefs that have been severely affected by recent climate change. This adaptive shift in symbiont communities indicates that these devastated reefs could be more resistant to future thermal stress, resulting in significantly longer extinction times for surviving corals than had been previously assumed.