Rapid Arctic warming and sea-ice reduction in the Arctic Ocean are widely attributed to anthropogenic climate change. The Arctic warming exceeds the global average warming because of feedbacks that include sea-ice reduction and other dynamical and radiative feedbacks. We find that the most prominent annual mean surface and tropospheric warming in the Arctic since 1979 has occurred in northeastern Canada and Greenland. In this region, much of the year-to-year temperature variability is associated with the leading mode of large-scale circulation variability in the North Atlantic, namely, the North Atlantic Oscillation. Here we show that the recent warming in this region is strongly associated with a negative trend in the North Atlantic Oscillation, which is a response to anomalous Rossby wave-train activity originating in the tropical Pacific. Atmospheric model experiments forced by prescribed tropical sea surface temperatures simulate the observed circulation changes and associated tropospheric and surface warming over northeastern Canada and Greenland. Experiments from the Coupled Model Intercomparison Project Phase 5 (ref. 16) models with prescribed anthropogenic forcing show no similar circulation changes related to the North Atlantic Oscillation or associated tropospheric warming. This suggests that a substantial portion of recent warming in the northeastern Canada and Greenland sector of the Arctic arises from unforced natural variability.