Can multi-annual variations in the frequency of North Atlantic atmospheric blocking and mid-latitude circulation regimes be skilfully predicted? Recent advances in seasonal forecasting have shown that mid-latitude climate variability does exhibit significant predictability. However, atmospheric predictability has generally been found to be quite limited on multi-annual timescales. New decadal prediction experiments from NCAR are found to exhibit remarkable skill in reproducing the observed multi-annual variations of wintertime blocking frequency over the North Atlantic and of the North Atlantic Oscillation (NAO) itself. This is partly due to the large ensemble size that allows the predictable component of the atmospheric variability to emerge from the background chaotic component. The predictable atmospheric anomalies represent a forced response to oceanic low-frequency variability that strongly resembles the Atlantic Multi-decadal Variability (AMV), correctly reproduced in the decadal hindcasts thanks to realistic ocean initialization and ocean dynamics. The occurrence of blocking in certain areas of the Euro-Atlantic domain determines the concurrent circulation regime and the phase of known teleconnections, such as the NAO, consequently affecting the stormtrack and the frequency and intensity of extreme weather events. Therefore, skillfully predicting the decadal fluctuations of blocking frequency and the NAO may be used in statistical predictions of near-term climate anomalies, and it provides a strong indication that impactful climate anomalies may also be predictable with improved dynamical models.