Based on the gridded daily surface air temperature database (V2.0) of China, the influences of wintertime North Atlantic Oscillation (NAO) on extreme low temperature over northern China are investigated. The interdecadal variation in the relationship between NAO and cold days (nights) during the same period over Northeast China (NEC) in late winter is revealed based on sliding correlation analysis and correlation analysis. The results show that cold days (nights) are more frequent in late winter over NEC and have a better correlation with NAO before the middle 1980s compared to that after the middle 1980s. Additionally, the correlation was most significant over NEC in January during the period of 1969-1988, which could reach −0.68 (−0.66), but became weak during the period of 1989-2009. Furthermore, it is found that the interdecadal variation in the relationship between NAO and cold days (nights) over NEC in January is largely attributed to the NAO-related atmospheric circulation anomalies under different interdecadal backgrounds. The weather systems such as cold vortex caused by the NAO-related atmospheric circulation anomalies can maintain over a large area from Lake Baikal to NEC, leading to lower than normal temperature and more frequent cold days (nights) over NEC in the years when significant correlation exists between NAO and cold days (nights). The opposite is true when there is no significant correlation between NAO and cold days (nights) in NEC.