Although the long-term trend of extreme temperatures has been extensively explored in previous studies, few studies have addressed the interdecadal variation of extreme temperatures. Based on the daily maximum temperature, minimum temperature, and daily temperature at 839 stations in China from 1961 to 2016, the authors analyzed the interdecadal variations in the winter extreme-low-temperature index in China. The first four wave components of the extreme temperature at each station were extracted by harmonic decomposition, which is regarded as the interdecadal component. A station is regarded as having undergone an obvious interdecadal variation if the cumulative variance explained by the interdecadal component is greater than 25%. The results show that the stations with obvious interdecadal variation in their winter extreme-low-temperature index are mainly located north of the Yangtze River, in northern Xinjiang, and in eastern Qinghai–Tibet Plateau. The interdecadal variations north of the Yangtze River and in northern Xinjiang are basically consistent after 1979. The years after 1979 can be divided into three periods: previously cold period (1979–1986), warm period (1987–2007), and later-cold period (2008–2016). The interdecadal variation in the extreme temperature indices of the stations located in the abovementioned two areas might be modulated by the interdecadal variation in the East Atlantic/West Russia (EAWR) teleconnection pattern, which corresponds to the interdecadal variation in both the frequency of the blocking-like circulation over the Ural Mountains and the amplitude of the planetary trough over East Asia.