Tropical reefs have been impacted by thermal anomalies caused by global warming that induced coral bleaching and mortality events globally. However, there have only been very few recordings of bleaching within the Red Sea despite covering a latitudinal range of 15° and consequently it has been considered a region that is less sensitive to thermal anomalies. We therefore examined historical patterns of sea surface temperature (SST) and associated anomalies (1982–2012) and compared warming trends with a unique compilation of corresponding coral bleaching records from throughout the region. These data indicated that the northern Red Sea has not experienced mass bleaching despite intensive Degree Heating Weeks (DHW) of >15°C-weeks. Severe bleaching was restricted to the central and southern Red Sea where DHWs have been more frequent, but far less intense (DHWs 8°C-weeks), and bleaching was restricted to the central and southern Red Sea despite the lower thermal stress (DHWs < 8°C-weeks). Heat stress assays carried out in the northern (Hurghada) and central (Thuwal) Red Sea on four key reef-building species confirmed different regional thermal susceptibility, and that central Red Sea corals are more sensitive to thermal anomalies as compared to those from the north. Together, our data demonstrate that corals in the northern Red Sea have a much higher heat tolerance than their prevailing temperature regime would suggest. In contrast, corals from the central Red Sea are close to their thermal limits, which closely match the maximum annual water temperatures. The northern Red Sea harbours reef-building corals that live well below their bleaching thresholds and thus we propose that the region represents a thermal refuge of global importance.