Satellite data suggest an Arctic sea ice-climate system in rapid transformation, yet its long-term natural modes of variability are poorly known. Here we integrate and synthesize a set of multicentury historical records of Atlantic Arctic sea ice, supplemented with high-resolution paleoproxy records, each reflecting primarily winter/spring sea ice conditions. We establish a signal of pervasive and persistent multidecadal (~60–90 year) fluctuations that is most pronounced in the Greenland Sea and weakens further away. Covariability between sea ice and Atlantic multidecadal variability as represented by the Atlantic Multidecadal Oscillation (AMO) index is evident during the instrumental record, including an abrupt change at the onset of the early twentieth century warming. Similar covariability through previous centuries is evident from comparison of the longest historical sea ice records and paleoproxy reconstructions of sea ice and the AMO. This observational evidence supports recent modeling studies that have suggested that Arctic sea ice is intrinsically linked to Atlantic multidecadal variability. This may have implications for understanding the recent negative trend in Arctic winter sea ice extent, although because the losses have been greater in summer, other processes and feedbacks are also important.