An analysis of satellite sea-ice records for recent decades reveals a highly coherent spatial and temporal structure of the Northern Hemisphere (NH) wintertime sea-ice variability and its close link to anomalous atmospheric circulation. The dominant mode of the wintertime sea-ice variability is characterized by a double-dipole composed of one dipole over the North Atlantic and the other over the North Pacific, which are mutually correlated interannually. This dominant sea-ice mode is lag correlated with the winter-averaged North Atlantic Oscillation (NAO) index at lags up to two winters when the NAO leads. In the sub-Arctic, significant lead–lag relationships exist between sea-ice extent (SIE) anomalies on regional scales, which are closely associated with atmospheric circulation anomalies. An eastward evolving pattern is identified in regional SIE anomalies from the Labrador to Nordic and farther to the Okhotsk Sea at multi-year time-scales, led by anomalously weak Aleutian and strong Icelandic lows. The results suggest the presence of climate memories over the North Atlantic and Eurasia, which are crucial for recent downward trends in the NH SIE by transforming atmospheric influences into slower changes in sea-ice conditions. The summer Okhotsk high, which leads to a sea-ice reduction along the east Siberian coast and further affects sea-ice conditions over the Arctic Ocean, is a key link between summer Arctic and winter sub-Arctic sea-ice trends. We also conjecture that variations and changes in the NH sea-ice conditions are linked to climate variability in the tropics.