Climate fluctuations in the North Atlantic Ocean have wide-spread implications for Europe, Africa, and the Americas. This study assesses the relative contribution of long-term trend and variability of the North Atlantic warming using EOF analysis of deep-ocean and near-surface observations. Our analysis demonstrates that the recent warming over the North Atlantic is linked to both long-term (including anthropogenic and natural) climate change and multidecadal variability (MDV, ~50-80 years). Our results suggest a general warming trend of 0.031±0.006oC/decade in the upper 2000m North Atlantic over the last 80 years of the twentieth century, although during this time there are periods in which short-term trends were strongly amplified by MDV. For example, MDV accounts for ~60% of North Atlantic warming since 1970. The single-sign basin-scale pattern of MDV with prolonged periods of warming (cooling) in the upper ocean layer and opposite tendency in the lower layer is evident from observations. This pattern is consistent with a slowdown of the North Atlantic thermohaline overturning circulation. In contrast, the long-term trend exhibits warming in tropical and mid-latitude North Atlantic and a pattern of cooling in regions associated with major northward heat transports, consistent with a slowdown of the North Atlantic circulation as evident from observations and modeling results. This localized cooling has been masked in recent decades by warming during the positive phase of MDV. Finally, since the North Atlantic Ocean plays a crucial role in establishing and regulating global thermohaline circulation, the multidecadal fluctuations discussed here should be considered when assessing long-term climate change and variability, both in the North Atlantic and at global scales.