Recent observations of warming trends in the Red Sea raise more attention to the response of the basin under a warming climate. Using two remotely sensed datasets, the Hadley Centre Sea Ice and Sea Surface Temperature [HadISST] and Extended Reconstructed Sea Surface Temperature [ERSST.v3], we investigate the reported sudden increase in the Red Sea sea surface temperatures (SST) in terms of average and maximum and assess their relation to multi-decadal climate variability. Prior to the analysis, the two datasets are successfully validated with respect to their ability to reproduce the recent observed and reported trends and their spatial features. Analysis of long-term SST variability revealed a sequence of alternating and similar in amplitude positive and negative trends, characterized by a period of nearly 70 years. Similar oscillations have been reported in other basins and have been related to atmospheric disturbances associated with the Atlantic Multidecadal Oscillation (AMO). A point-by-point spectral analysis of SST evolution shows a significant correlation with the basic modes of the AMO that explains a large fraction of its temporal and spatial variability. Projections on the major modes of the spectral analysis suggest a possible decreasing effect on local SST in the near future. Under this assumption, recent projected trends in the Red Sea may be exaggerated, whilst trends that may be related to anthropogenic influence could be masked by the projected negative influence of the AMO in the near future.