The twentieth century Northern Hemisphere mean surface temperature (NHT) is characterized by a multidecadal warming-cooling-warming pattern followed by a flat trend since about 2000 (recent warming hiatus). Here we demonstrate that the North Atlantic Oscillation (NAO) is implicated as a useful predictor of NHT multidecadal variability. Observational analysis shows that the NAO leads both the detrended NHT and oceanic Atlantic Multidecadal Oscillation (AMO) by 15–20 years. Theoretical analysis illuminates that the NAO precedes NHT multidecadal variability through its delayed effect on the AMO due to the large thermal inertia associated with slow oceanic processes. An NAO-based linear model is therefore established to predict the NHT, which gives an excellent hindcast for NHT in 1971–2011 with the recent flat trend well predicted. NHT in 2012–2027 is predicted to fall slightly over the next decades, due to the recent NAO decadal weakening that temporarily offsets the anthropogenically induced warming.