Sea ice is a critical component of the climate system: variations in sea-ice cover affect the albedo of polar regions, and also the rate of deepwater formation. Changes in the sea-ice cover of the North Atlantic Ocean are thought to have been related to abrupt climate changes throughout the last glacial termination, but reconstructions of sea-ice conditions are rare. Here we use the sedimentary abundance of the IP 25 and brassicasterol biomarkers, produced by sea-ice-associated diatoms and open-water phytoplankton, respectively, to generate a record of sea-ice conditions in the northernmost Atlantic Ocean for the past 30,000 years. Our reconstruction shows that a stationary margin between sea-ice cover and the open ocean existed during the Last Glacial, although perennial sea-ice cover prevailed for most of the Last Glacial Maximum. An early warming about 14,000 years ago was associated with ice-free conditions; however, seasonal sea ice was present throughout the Holocene. We find temporal links between our record of sea ice and reconstructions of the amount of relatively warm Atlantic water advected into the Nordic Seas. We therefore conclude that changes in sea-ice conditions are linked to regional and global climate anomalies and oceanographic circulation in the North Atlantic. © 2009 Macmillan Publishers Limited. All rights reserved.