Twenty-four years of AVHRR-derived sea surface temperature (SST) data (1985–2008) and 35 years of NOCS (V.2) in situ-based SST data (1973–2008) were used to investigate the decadal scale variability of this parameter in the Mediterranean Sea in relation to local air–sea interaction and large-scale atmospheric variability. Satellite and in situ-derived data indicate a strong eastward increasing sea surface warming trend from the early 1990s onwards. The satellite-derived mean annual warming rate is about 0.037°C year–1 for the whole basin, about 0.026°C year–1 for the western sub-basin and about 0.042°C year–1 for the eastern sub-basin over 1985–2008. NOCS-derived data indicate similar variability but with lower warming trends for both sub-basins over the same period. The long-term Mediterranean SST spatiotemporal variability is mainly associated with horizontal heat advection variations and an increasing warming of the Atlantic inflow. Analysis of SST and net heat flux inter-annual variations indicates a negative correlation, with the long-term SST increase, driving a net air–sea heat flux decrease in the Mediterranean Sea through a large increase in the latent heat loss. Empirical orthogonal function (EOF) analysis of the monthly average anomaly satellite-derived time series showed that the first EOF mode is associated with a long-term warming trend throughout the whole Mediterranean surface and it is highly correlated with both the Eastern Atlantic (EA) pattern and the Atlantic Multidecadal Oscillation (AMO) index. On the other hand, SST basin-average yearly anomaly and NAO variations show low and not statistically significant correlations of opposite sign for the eastern (negative correlation) and western (positive correlation) sub-basins. However, there seems to be a link between NAO and SST decadal-scale variations that is particularly evidenced in the second EOF mode of SST anomalies. NOCS SST time series show a significant SST rise in the western basin from 1973 to the late 1980s following a large warming of the inflowing surface Atlantic waters and a long-term increase of the NAO index, whereas SST slowly increased in the eastern basin. In the early 1990s, there is an abrupt change from a very high positive to a low NAO phase which coincides with a large change in the SST spatiotemporal variability pattern. This pronounced variability shift is followed by an acceleration of the warming rate in the Mediterranean Sea and a change in the direction (from westward to eastward) of its spatial increasing tendency.