The North Atlantic Oscillation (NAO) is the key indicator of long-term variability in the North Atlantic. Numerous studies have accepted as a paradigm a steady relationship between the NAO and key North Atlantic climate parameters like the sea surface temperature (SST), surface air temperature (SAT), and sea level pressure (SLP). However, some studies suggest that this relationship is not always steady. For example, the recent decline of the Arctic ice cap is accompanied by a neutral or negative NAO index, whereas the ice decline observed over the last decades is associated with the positive NAO phase and with high atmospheric cyclonicity. In this study, we point to a lack of steadiness in the relationship between the NAO and SAT, SST, and SLP over the North Atlantic region when observed over long (decadal) time intervals. This suggests that the relationship is more complex than previously thought and may require further investigation.