Based on 1979-2011 daily surface temperature data collected at 119 stations in Northeast China, the decadal variability of cold waves across Northeast China was investigated. The possible causes for the decadal changes were also discussed through analyzing changes in atmospheric circulation and Arctic sea ice. The frequency and intensity of spring cold waves across Northeast China both changed at the end of the 1980s and in the early 2000s. Cold waves in the 1990s were less frequent but stronger than those in the 1980s, and less frequent but weaker than those in the 2000s. The change in sea ice concentration around Novaya Zemlya was a possible cause for the decadal variability of spring cold waves in Northeast China. Rapid decrease in sea ice in Novaya Zemlya significantly increased surface air temperature (SAT) and weakened sea level pressure (SLP) in the high latitudes around this region, which were not favorable for the southward movement of cold air over Novaya Zemlya. In addition, the decrease in sea ice cover around this area and the deep East Asia trough could also lead to the strengthening of cold waves across Northeast China, while the cold waves in the 2000s became weaker but occurred more frequently possibly due to a slower decrease trend of sea ice cover in Novaya Zemlya.