The overflow of deep water from the Nordic seas into the North Atlantic plays a critical role in global ocean circulation and climate. Approximately half of this overflow occurs via the Iceland-Scotland (I-S) overflow, yet the history of its strength throughout the Holocene (similar to 0-11 700 yr ago, ka) is poorly constrained, with previous studies presenting apparently contradictory evidence regarding its long-term variability. Here, we provide a comprehensive reconstruction of I-S overflow strength throughout the Holocene using sediment grain size data from a depth transect of 13 cores from the Iceland Basin. Our data are consistent with the hypothesis that the main axis of the I-S overflow on the Iceland slope was shallower during the early Holocene, deepening to its present depth by similar to 7 ka. Our results also reveal weaker I-S overflow during the early and late Holocene, with maximum overflow strength occurring at similar to 7 ka, the time of a regional climate thermal maximum. Climate model simulations suggest a shoaling of deep convection in the Nordic seas during the early and late Holocene, consistent with our evidence for weaker I-S overflow during these intervals. Whereas the reduction in I-S overflow strength during the early Holocene likely resulted from melting remnant glacial ice sheets, the decline throughout the last 7000 yr was caused by an orbitally induced increase in the amount of Arctic sea ice entering the Nordic seas. Although the flux of Arctic sea ice to the Nordic seas is expected to decrease throughout the next century, model simulations predict that under high emissions scenarios, competing effects, such as warmer sea surface temperatures in the Nordic seas, will result in reduced deep convection, likely driving a weaker I-S overflow.