Abstract: In this paper, the relationship of interannual variation between spring sea surface temperature anomaly in the North Atlantic and extreme cold event (ECE) frequency in eastern China is investigated. The results show that not before but after the late 1980s, the North Atlantic tripolar SST mode (NATSST) has significantly affected the first leading mode of ECE frequency in eastern China. Further mechanistic analysis suggests that such an interdecadal change in their relationship could be related to the difference in the NATSST-excited wave trains before and after the late 1980s. In 1960–1987, the NATSST-related wave train propagated from the North Atlantic to southern Central Asia, which was located more southward, and consequently, had a weak influence on atmospheric circulations and ECE in eastern China. However, in 1992–2019, NATSST could excite two wave trains. The northern train was associated with the North Atlantic Oscillation, propagating eastward from the North Atlantic to the mid-high latitudes of Eurasia, resulting in an anomalous cyclonic/anticyclonic circulation in the Mongolian region. The southern train propagated eastward from the North Atlantic to the mid-low latitudes of Eurasia, leading to an anomalous cyclonic/anticyclonic circulation in southern–central China. These cyclonic and anticyclonic circulations are, respectively, favorable and unfavorable to the southward movement of cold air from middle and high latitudes and change the surface heat flux in eastern China, consequently providing favorable and unfavorable climate background conditions for ECE occurrence. Through these physical processes, NATSST could significantly influence the interannual variability of the frequency of spring ECE in eastern China after the late 1980s, but not before that.