Species intolerant of changing climate might avoid extinction within refugia buffered from extreme conditions. Refugia have been observed in the fossil record but are not well-documented or understood on ecological time scales. Using a 37-year record from the eastern Pacific across the two most severe El Niño events on record (1982–83 and 1997–98) we show how an exceptionally thermally-sensitive reef-building hydrocoral, Millepora intricata, twice survived catastrophic bleaching in a deeper water refuge (>11 m depth). During both events, M. intricata was extirpated across its range in shallow water but showed recovery within several years, while two other hydrocorals without deep-water populations were driven to regional extinction. Evidence from the sub-fossil record in the same area showed shallow-water persistence of abundant M. intricata populations from 5000 years ago, through severe El Niño–Southern Oscillation cycles, suggesting a potential depth refugium on a millennial timescale. Our data confirm the deep refuge hypothesis for corals under thermal stress.