Northern Hemisphere sea ice has been declining sharply over the past decades and 2012 exhibited the lowest Arctic summer sea-ice cover in historic times. Whereas ongoing changes are closely monitored through satellite observations, we have only limited data of past Arctic sea-ice cover derived from short historical records, indirect terrestrial proxies, and low-resolution marine sediment cores. A multicentury time series from extremely long-lived annual increment-forming crustose coralline algal buildups now provides the first high-resolution in situ marine proxy for sea-ice cover. Growth and Mg/Ca ratios of these Arctic-wide occurring calcified algae are sensitive to changes in both temperature and solar radiation. Growth sharply declines with increasing sea-ice blockage of light from the benthic algal habitat. The 646-y multisite record from the Canadian Arctic indicates that during the Little Ice Age, sea ice was extensive but highly variable on subdecadal time scales and coincided with an expansion of ice-dependent Thule/Labrador Inuit sea mammal hunters in the region. The past 150 y instead have been characterized by sea ice exhibiting multidecadal variability with a long-term decline distinctly steeper than at any time since the 14th century.