Many previous studies have examined the influence of Arctic sea ice on the weather/climate of the Northern Hemisphere. However, the precursor signals of Arctic sea ice regarding East Asian winter low temperatures, which are important for climate prediction, have received little attention. This study identified an out-of-phase relation between the autumn sea ice area of the Kara Sea (SICK) and subsequent winter minimum temperatures in Northeast China (NEC) during 1979–2019, i.e., diminished SICK facilitates cooling anomalies at NEC. Further results showed that the Arctic Oscillation (AO) acts as a bridge in the linkage between the autumn SICK and minimum temperature in NEC. Diminished autumn SICK leads to a weakened polar vortex in both the troposphere and the stratosphere in the subsequent winter through vertical propagation of planetary waves, contributing to a negative phase of the AO. Accordingly, the SICK is followed by anomalous Rossby wave train that originates from Mediterranean Sea and propagates eastward to Northeast Asia. Thus, the SICK has substantially influence on the Mongolia cyclone and minimum temperature in NEC by modulation of the AO. Moreover, the shrinking SICK could lead to the upper-level decelerated westerly anomalies at East Asia through altering the equator-to-pole temperature gradient and induce negative minimum temperature anomalies at NEC. The results of this study have importance regarding the prediction of low temperature anomalies over NEC.