The close decadal relationship between the North Atlantic Oscillation (NAO) and the cold surge frequency in Northern Taiwan is identified. The cold surge frequency was higher (lower) in 1957–1977 (1981–2001), which corresponded to the negative (positive) phase of the NAO. The teleconnection pattern associated with the NAO suggests that the Siberian high, the ridge upstream of Lake Baikal and the East Asian trough, which are well-known circulation characteristics favorable for cold surge occurrences, were enhanced in the negative NAO phase. A weakened upper-level convergence over the Mediterranean-Sahara occurring in the negative NAO phase was associated with a wave-like pattern spreading toward East Asia along the subtropical jet stream. Barotropic modeling results suggest that the suppressed upper-level convergence in the Mediterranean-Sahara region may force a wave train emanating toward East Asia along the subtropical jet stream, which acts as a Rossby waveguide. The barotropic wave pattern may result in a stronger low-level northerly over subtropical East Asia and create a favorable background for the further southward penetration of cold air, and therefore more frequent cold surge occurrence. The same process may be applied to the period when the NAO is in the positive phase.