The fast decline of Arctic sea ice is a leading indicator of ongoing global climate change and is receiving substantial public and scientific attention. Projections suggest that Arctic summer sea ice may virtually disappear within the course of the next 50 or even 30 yr with rapid Arctic warming. However, limited observational records and lack of annual-resolution marine sea-ice proxies hamper the assessment of long-term changes in sea ice, leading to large uncertainties in predictions of its future evolution under global warming. Here, we use long-lived encrusting coralline algae that strongly depend on light availability as a new in situ proxy to reconstruct past variability in the duration of seasonal sea-ice cover. Our data represent the northernmost annual-resolution marine sea-ice reconstruction to date, extending to the early 19th century off Svalbard. Algal records show that the decreasing trend in sea-ice cover in the high Arctic had already started at the beginning of the 20th century, earlier than previously reported from sea-ice reconstructions based on terrestrial archives. Our data further suggest that, although sea-ice extent varies on multidecadal time scales, the lowest sea-ice values within the past 200 yr occurred at the end of the 20th century.