Although recent reports suggest that the negative correlation between the Arctic Oscillation (AO) and the East Asian winter monsoon (EAWM) has been strengthened, it is not clear whether this intermittent relationship is an intrinsic oscillation in the climate system. We investigate the oscillating behavior of the AO-EAWM relationship at decadal time scales using the long-term (500-yr) climate model simulation. The results show that ice cover over the East Siberian Seas is responsible for the change in the coupling strength between AO and EAWM. We found that increased ice cover over these seas strengthens the AO-EAWM linkage, subsequently enhancing cold advection over the East Asia due to anomalous northerly flow via a weakened jet stream. Thus, this strengthened relationship favors more frequent occurrences of cold surges in the EAWM region. Results also indicate that the oscillating relationship between AO and EAWM is a natural variability without anthropogenic drivers, which may help us understand the AO-EAWM linkage under climate change.