Recent reports of warming trends in the Red Sea raise concerns about the response of the basin's fragile ecosystem under an increasingly warming climate. Using a variety of available Sea Surface Temperature (SST) datasets, we investigate the evolution of Red Sea SST in relation to natural climate variability. Analysis of long-term SST datasets reveals a sequence of alternating positive and negative trends, with similar amplitudes and a periodicity of nearly 70 years associated with the Atlantic Multidecadal Oscillation (AMO). High warming rates reported recently appear to be a combined effect of global warming and a positive phase of natural SST oscillations. Over the next decades, the SST trend in the Red Sea purely related to global warming is expected to be counteracted by the cooling AMO phase. Regardless of the current positive trends, projections incorporating long-term natural oscillations suggest a possible decreasing effect on SST in the near future.