The East Asian winter monsoon (EAWM) and the North Pacific Oscillation (NPO) constitute two outstanding surface atmospheric circulation patterns affecting the winter sea surface temperature (SST) variability in the western North Pacific. The present analyses show the relationship between the EAWM and NPO and their impact on the SST are nonstationary and regime-dependent with a sudden change around 1988. These surface circulation patterns are tightly linked to the upper-level Ural and Kamchatka blockings, respectively. During the 1973–87 strong winter monsoon epoch, the EAWM and NPO were significantly correlated to each other, but their correlation practically vanishes during the 1988–2002 weak winter monsoon epoch. This nonstationary relationship is related to the pronounced decadal weakening of the Siberian high system over the Eurasian continent after the 1988 regime shift as well as the concomitant positive NPO-like dipole change and its eastward migration in tropospheric circulation over the North Pacific. There is a tight tropical–extratropical teleconnection in the western North Pacific in the strong monsoon epoch, which disappears in the weak monsoon epoch when there is a significant eastward shift of tropical influence and enhanced storm tracks into the eastern North Pacific. A tentative mechanism of the nonstationary relationship between the EAWM and NPO is proposed, stressing the pivotal role played in the above teleconnection by a decadal shift of the East Asian trough resulting from the abrupt decline of the EAWM since the late 1980s.