The North Atlantic Oscillation (NAO) has a profound effect on winter climate variability around the Atlantic basin. Strengthening of the NAO in recent decades has altered surface climate in these regions at a rate far in excess of global mean warming. However, only weak NAO trends are reproduced in climate simulations of the 20th Century, even with prescribed climate forcings and historical sea-surface conditions. Here we show that the unexplained strengthening of the NAO can be fully simulated in a climate model by imposing observed trends in the lower stratosphere. This implies that stratospheric variability needs to be reproduced in models to fully simulate surface climate variations in the North Atlantic sector. Despite having little effect on global mean warming, we show that downward coupling of observed stratospheric circulation changes to the surface can account for the majority of change in regional surface climate over Europe and North America between 1965 and 1995.