Evidence is presented that the correlation between the North Atlantic Oscillation (NAO), in terms of the NAO index, and the North Atlantic sea surface temperature (SST) is not stationary. This is inferred from both reanalysis data from the U.S. National Centers for Environmental Prediction/National Center for Atmospheric Research (NCEP/NCAR) and the Kaplan sea surface temperature data set. Two phases of winterly North Atlantic atmosphere-ocean covariability are identified by means of linear regression and correlation analysis. During the recent decades since the late 1960s/early 1970s and during the first 3 decades of the twentieth century, the North Atlantic SST is strongly correlated to the regional atmospheric circulation in the North Atlantic sector, i.e., the North Atlantic Oscillation. During these periods the NAO index, defined as the difference of normalized sea level pressures on the Azores and Iceland, is characterized by pronounced decadal variability and by mainly positive values. In contrast, the NAO index is only weakly correlated to the North Atlantic SST from the 1930s to the early 1960s, when the NAO index is characterized by weak decadal variability. Remote influences, in particular from the tropical Pacific region, become important, especially for the SST in the western tropical North Atlantic.