Coinciding with global warming, Arctic sea ice has rapidly decreased during the last four decades and climate scenarios suggest that sea ice may completely disappear during summer within the next about 50-100 years. Here we produce Arctic sea ice biomarker proxy records for the penultimate glacial (Marine Isotope Stage 6) and the subsequent last interglacial (Marine Isotope Stage 5e). The latter is a time interval when the high latitudes were significantly warmer than today. We document that even under such warmer climate conditions, sea ice existed in the central Arctic Ocean during summer, whereas sea ice was significantly reduced along the Barents Sea continental margin influenced by Atlantic Water inflow. Our proxy reconstruction of the last interglacial sea ice cover is supported by climate simulations, although some proxy data/model inconsistencies still exist. During late Marine Isotope Stage 6, polynya-type conditions occurred off the major ice sheets along the northern Barents and East Siberian continental margins, contradicting a giant Marine Isotope Stage 6 ice shelf that covered the entire Arctic Ocean.