Temperature reconstructions from the Northern Hemisphere (NH) generally indicate cooling over the Holocene, which is often attributed to decreasing summer insolation. However, climate model simulations predict that rising atmospheric CO2 concentrations and the collapse of the Laurentide Ice Sheet caused mean annual warming during this epoch. This contrast could reflect a seasonal bias in temperature proxies, and particularly a lack of proxies that record cold (late fall–early spring) season temperatures, or inaccuracies in climate model predictions of NH temperature. We reconstructed winter–spring temperatures during the Common Era (i.e., the last 2000 years) using alkenones, lipids produced by Isochrysidales haptophyte algae that bloom during spring ice-out, preserved in sediments from Vestra Gíslholtsvatn (VGHV), southwest Iceland. Our record indicates that winter–spring temperatures warmed during the last 2000 years, in contrast to most NH averages. Sensitivity tests with a lake energy balance model suggest that warmer winter and spring air temperatures result in earlier ice-out dates and warmer spring lake water temperatures and therefore warming in our proxy record. Regional air temperatures are strongly influenced by sea surface temperatures during the winter and spring season. Sea surface temperatures (SSTs) respond to both changes in ocean circulation and gradual changes in insolation. We also found distinct seasonal differences in centennial-scale, cold-season temperature variations in VGHV compared to existing records of summer and annual temperatures from Iceland. Multi-decadal to centennial-scale changes in winter–spring temperatures were strongly modulated by internal climate variability and changes in regional ocean circulation, which can result in winter and spring warming in Iceland even after a major negative radiative perturbation.