One of the most prominent and important features of climate change is that surface air temperature (SAT) change is greatest at high latitudes. The cause for this Arctic amplification of SAT is uncertain. Using ERA-Interim reanalysis data, we show that Arctic amplification during the past 30 years (1979 to 2008) is linked to the Madden-Julian Oscillation (MJO), the primary mode of intraseasonal variability in the tropics. Specifically, it is shown that interdecadal changes in the frequency of occurrence of individual MJO phases have had considerable influence on the Arctic warming during the boreal winter. During that time period, MJO phases 4–6 exhibited a large increase and phases 1–2 a moderate decrease in their frequency of occurrence. Time lagged composites of the SAT show that MJO phases 4–6, which correspond to enhanced localized tropical heating, are followed 1–2 weeks later by Arctic warming. Similarly, MJO phases 1–2, which are associated with more zonally uniform tropical heating, are followed by Arctic cooling. These relationships between the Arctic SAT and the spatial structure of the tropical heating are consistent with the poleward propagation mechanism of Lee et al. (2011a, 2011b). By incorporating both the trend in MJO phase and the intraseasonal SAT anomaly associated with the MJO, it was found that the MJO-induced SAT trend accounts for 10–20% of the observed Arctic amplification over the Arctic Ocean.