The variability of Arctic sea-ice during abrupt stadial-interstadial shifts in the last glacial period remain poorly understood. Here, we investigated the millennial-scale relationship, with a focus on Heinrich Stadials (HS), between sea-ice cover and bottom water temperature (BWT) during Marine Isotope Stages (MIS) 3 and 2 (64–13 ka) in the Fram Strait using new molecular sea ice biomarker data and published benthic foraminiferal BWT records. Widespread spring sea-ice cover (SpSIC) dominated the studied interval, especially in mid-late MIS 3 (45–29 ka). Yet, warm interstadials were characterized by relatively more open-ocean conditions compared to cold stadials. At the transition between a HS and the subsequent interstadial, sea ice was tightly linked to BWT with rapid reductions in SpSIC coinciding with lower BWT at the end of HS. The relative timing of the events, especially during HS 1, points to ocean warming as the key controlling factor for sea ice reduction at millennial timescales.