The wintertime warm Arctic-cold Eurasia (WACE) temperature trend during 1990-2010 was characterized by accelerating warming in the Arctic region, cooling in Eurasia, and accelerating autumn/winter Arctic sea ice loss. We identify two atmospheric circulation modes over the North Atlantic-northern Eurasian sector that displayed strong upward trends over the same period and can explain a large part of the observed decadal WACE pattern. Both modes bear a close resemblance to well-known teleconnection patterns and are relatively independent from variability in Arctic sea ice cover. The first mode (PC1) captures the recent negative trends in the North Atlantic Oscillation and increased Greenland blocking frequency, while the second mode (PC2) is reminiscent of a Rossby wave train and reflects an increased blocking frequency over the Urals and north Asia. We find that the loss in the Arctic sea ice and the upward trends in PC1 and PC2 together account for most of the decadal Arctic warming trend (>80%). However, the decadal Eurasian cooling trends may be primarily ascribed to the two circulation modes alone: all of the cooling in Siberia is contributed to by PC1 and 65% of the cooling in East Asia by their combination (the contribution by PC2 doubles that by PC1). Enhanced intraseasonal activity of the two circulation modes increases blocking frequencies over Greenland, the Ural region, and north Asia, which drive anomalous moisture/heat flux toward the Arctic and alter the downward longwave radiation. This also weakens warm advection and enhances advection of cold Arctic airmasses towards Eurasia.