Although the daily weather of mid-latitude regions is largely unpredictable more than ten or so days in advance, the hope is that there may be a predictable element to the average weather of the season or even decade ahead. We present results from recent atmospheric model simulations which show, for the first time, a high degree of skill in capturing the observed fluctuations in pressure over the North Atlantic for the last 50 years. The same pattern of ocean-surface temperatures appears to be responsible for both the observed and simulated pressure variations. We suggest a mechanism, somewhat different from previous mechanisms, to explain how these sea-surface temperatures are communicated to the atmosphere. We also show how the atmospheric response may feed-back onto the ocean. Recently it has been proposed that there may be significant decadal predictability of North Atlantic sea-surface temperatures. If this does prove to be the case, then our results are encouraging for the prediction of natural variations in European climate up to a few years ahead