Holocene climate modes are identified by the statistical analysis of reconstructed sea surface temperatures (SSTs) from the tropical and North Atlantic regions. The leading mode of Holocene SST variability in the tropical region indicates a rapid warming from the early to the mid Holocene followed by a relatively weak warming during the late Holocene. The dominant mode of the North Atlantic region SST captures the transition from relatively warm (cold) conditions in the eastern North Atlantic and the western Mediterranean Sea (the northern Red Sea) to relatively cold (warm) conditions in these regions from the early to late Holocene. This pattern of Holocene SST variability resembles the signature of the Arctic Oscillation/North Atlantic Oscillation (AO/NAO). The second mode of both tropical and North Atlantic regions captures the warming towards the mid Holocene and subsequent neoglaciation. The dominant modes of Holocene SST variability emphasize enhanced variability around 2300 and 1000 years. The leading mode of the coupled tropical-North Atlantic Holocene SST variability shows that an increase of tropical SST is accompanied by a decrease of SST in the eastern North Atlantic. An analogy with the instrumental period as well as the analysis of a long-term integration of a coupled ocean-atmosphere general circulation model suggest that the AO/NAO is one dominant mode of climate variability at millennial time scales.