Declining sea-ice extent is currently amplifying climate warming in the Arctic. Instrumental records at high latitudes are too short-term to provide sufficient historical context for these trends, so paleoclimate archives are needed to better understand the functioning of the sea ice-albedo feedback. Here we use the oxygen isotope values of wood cellulose in living and sub-fossil willow shrubs (δ¹⁸O_wc) (Salix spp.) that have been radiocarbon-dated (¹⁴C) to produce a multi-millennial record of climatic change on Alaska's North Slope during the Pleistocene-Holocene transition (13,500–7500 calibrated ¹⁴C years before present; 13.5–7.5 ka). We first analyzed the spatial and temporal patterns of δ¹⁸O_wc in living willows growing at upland sites and found that over the last 30 years δ¹⁸O_wc values in individual growth rings correlate with local summer temperature and inter-annual variations in summer sea-ice extent. Deglacial δ¹⁸O_wcvalues from 145 samples of subfossil willows clearly record the Allerød warm period (∼13.2 ka), the Younger Dryas cold period (12.9–11.7 ka), and the Holocene Thermal Maximum (11.7–9.0 ka). The magnitudes of isotopic changes over these rapid climate oscillations were ∼4.5‰, which is about 60% of the differences in δ¹⁸O_wc between those willows growing during the last glacial period and today. Modeling of isotope-precipitation relationships based on Rayleigh distillation processes suggests that during the Younger Dryas these large shifts in δ¹⁸O_wc values were caused by interactions between local temperature and changes in evaporative moisture sources, the latter controlled by seaice extent in the Arctic Ocean and Bering Sea. Based on these results and on the effects that sea-ice have on climate today, we infer that ocean-derived feedbacks amplified temperature changes and enhanced precipitation in coastal regions of Arctic Alaska during warm times in the past. Today, isotope values in willows on the North Slope of Alaska are similar to those growing during the warmest times of the Pleistocene-Holocene transition, which were times of widespread permafrost thaw and striking ecological changes.