Ocean variability at decadal time-scales remains poorly described partly because of the scarcity of high temporal resolution marine records. Here, we present a reconstruction of Sea Surface Temperatures (SSTs) over the past two millennia at unprecedented temporal resolution (2 to 5 years), from a marine core located off North Iceland. Alkenone paleothermometry was used to infer SST variability, and tephrochronology to build the age model. Spectral analyses of the SST signal indicate intermittent 20–25 year oscillations, with periods of strong and weak power, that are likely reflecting the ocean response to wind forcing, presumably the North Atlantic Oscillation (NAO). Warmer SSTs and paleo-magnetic proxy data, between 1000 and 1350 year A.D., overlapping the Medieval Warm Period (MWP), suggest enhanced heat transport across the Denmark Strait by the North Icelandic Irminger Current (NIIC). This is in contrast with the subsequent period, which includes the Little Ice Age (LIA), showing continuous cooling towards the 20th century. Reduced NIIC flow through the Denmark Strait likely resulting from higher freshwater and sea ice export from the Arctic would account for the observed colder conditions.