Although it has been demonstrated that the speed and magnitude of recent Arctic sea ice decline is unprecedented for the past 1,450 years, few records are available to provide a paleoclimate context for Arctic sea ice extent. Here we present a 120 kyr record of bromine enrichment from the RECAP ice core, coastal East Greenland, and reconstruct past sea ice conditions in the North Atlantic as far north as the entrance of the Arctic Ocean (50–85° N). Bromine enrichment has been previously employed to reconstruct first-year sea ice (FYSI) in the Canadian Arctic over the last glacial cycle. We find that during the last deglaciation, the transition from multi-year sea ice (MYSI) to FYSI started at ∼ 17.6 kyr, synchronous with sea ice reductions observed in the eastern Nordic seas (Müller and Stein, 2014; Hoff et al., 2016) and with the increase of North Atlantic ocean temperature (Dokken and Jansen, 1999). FYSI reached its maximum extent at 12.4–11.8 kyr, after which open-water conditions started to dominate, as supported by sea ice records from the eastern Nordic seas and the North Icelandic shelf. Our results show that over the last 120,000 years, sea ice extent was greatest during Marine Isotope Stage (MIS) 2 and MIS4, with decreased levels during MIS3 and the onset of the last glacial period (late-MIS5). Sea ice extent during the last 10 kyr (Holocene/MIS1) has been less than at any time in the last 120 kyr.