Ocean warming is a major consequence of climate change, with the surface of the ocean having warmed by 0.11 °C decade⁻¹ over the last 50 years and is estimated to continue to warm by an additional 0.6 – 2.0 °C before the end of the century¹. However, there is considerable variability in the rates experienced by different ocean regions, so understanding regional trends is important to inform on possible stresses for marine organisms, particularly in warm seas where organisms may be already operating in the high end of their thermal tolerance. Although the Red Sea is one of the warmest ecosystems on earth, its historical warming trends and thermal evolution remain largely understudied. We characterized the Red Sea’s thermal regimes at the basin scale, with a focus on the spatial distribution and changes over time of sea surface temperature maxima, using remotely sensed sea surface temperature data from 1982 – 2015. The overall rate of warming for the Red Sea is 0.17 ± 0.07 °C decade⁻¹, while the northern Red Sea is warming between 0.40 and 0.45 °C decade⁻¹, all exceeding the global rate. Our findings show that the Red Sea is fast warming, which may in the future challenge its organisms and communities.