The North Atlantic is one of the few places on the globe where the atmosphere is linked to the deep ocean through air–sea interaction. While the internal variability of the atmosphere by itself is only predictable over a period of one to two weeks, climate variations are potentially predictable for much longer periods of months or even years because of coupling with the ocean. This work presents details from the first study to quantify the predictability for simulated multidecadal climate variability over the North Atlantic. The model used for this purpose is the GFDL coupled ocean-atmosphere climate model used extensively for studies of global warming and natural climate variability. This model contains fluctuations of the North Atlantic and high-latitude oceanic circulation with variability concentrated in the 40–60 year range. Oceanic predictability is quantified through analysis of the time-dependent behavior of large-scale empirical orthogonal function (EOF) patterns for the meridional stream function, dynamic topography, 170 m temperature, surface temperature and surface salinity. The results indicate that predictability in the North Atlantic depends on three main physical mechanisms. The first involves the oceanic deep convection in the subpolar region which acts to integrate atmospheric fluctuations, thus providing for a red noise oceanic response as elaborated by Hasselmann. The second involves the large-scale dynamics of the thermohaline circulation, which can cause the oceanic variations to have an oscillatory character on the multidecadal time scale. The third involves nonlocal effects on the North Atlantic arising from periodic anomalous fresh water transport advecting southward from the polar regions in the East Greenland Current. When the multidecadal oscillatory variations of the thermohaline circulation are active, the first and second EOF patterns for the North Atlantic dynamic topography have predictability time scales on the order of 10–20 y, whereas EOF-1 of SST has predictability time scales of 5–7 y. When the thermohaline variability has weak multidecadal power, the Hasselmann mechanism is dominant and the predictability is reduced by at least a factor of two. When the third mechanism is in an extreme phase, the North Atlantic dynamic topography patterns realize a 10–20 year predictability time scale. Additional analysis of SST in the Greenland Sea, in a region associated with the southward propagating fresh water anomalies, indicates the potential for decadal scale predictability for this high latitude region as well. The model calculations also allow insight into regional variations of predictability, which might be useful information for the design of a monitoring system for the North Atlantic. Predictability appears to break down most rapidly in regions of active convection in the high-latitude regions of the North Atlantic.