In the light of rapidly diminishing sea ice cover in the Arctic during the present atmospheric warming, it is imperative to study the distribution of sea ice in the past in relation to rapid climate change. Here we focus on glacial millennial-scale climatic events (Dansgaard/Oeschger events) using the sea ice proxy IP25 in combination with phytoplankton proxy data and quantification of diatom species in a record from the southeast Norwegian Sea. We demonstrate that expansion and retreat of sea ice varies consistently in pace with the rapid climate changes 90 kyr ago to present. Sea ice retreats abruptly at the start of warm interstadials, but spreads rapidly during cooling phases of the interstadials and becomes near perennial and perennial during cold stadials and Heinrich events, respectively. Low-salinity surface water and the sea ice edge spreads to the Greenland-Scotland Ridge, and during the largest Heinrich events, probably far into the Atlantic Ocean.