Atmospheric circulation may change with future climate change in response to modification of meridional temperature gradients, but the potential influence on ocean circulation is as yet unclear. Over the mid-late Holocene, atmospheric circulation in the North Atlantic region has fluctuated on millennial timescales; therefore, the ocean response to these changes can be investigated using the paleoceanographic records that have been developed in the north-eastern subpolar North Atlantic. Here, we present a diatom-based sea surface temperature reconstruction from the Iceland Basin, south of Iceland; the reconstruction shows the warmest temperatures of the record at 6.1e4 ka BP, cooler temperatures at 4-2 ka BP and warmer temperatures thereafter. Inter-record comparisons indicate that the cold period at c. 4- 2 ka BP may have resulted from a strengthened East Greenland Current and/or melting of the Greenland ice sheet, in response to a negative North Atlantic Oscillation. The findings highlight that atmospheric circulation changes are likely to cause pronounced variations in the latitudinal exchange of heat, which may have consequences for deep-water formation and global ocean circulation.