The variability in alkenone-derived sea surface temperatures (SSTs) in the North Atlantic realm shows that a continuous SST decrease in the northeast Atlantic from the early to the late Holocene was accompanied by a persistent warming over the western subtropical Atlantic, the eastern Mediterranean Sea and the northern Red Sea. Based on the analysis of the instrumental data and of atmospheric general circulation model experiments, we show that this variation in SSTs during the Holocene can be attributed to a continuous weakening of a Northern Hemisphere atmospheric circulation pattern similar to that of the Arctic/North Atlantic Oscillation.