A cooling trend in wintertime surface air temperature over continental Eurasia has been identified in reanalysis and the Coupled Model Inter-comparison Project phase 5 (CMIP5) ‘historical’ simulations over the period 1989-2009. Here the authors have shown that this cooling trend is related to changes in Arctic sea-ice around the Barents-Kara seas. This study illustrates a consistent spatial and temporal structure of the wintertime temperature variability centered over Asia using state-of-the-art reanalyses and global climate model datasets. Our findings indicate that there is a physical basis for seasonal predictions of near-surface temperatures over continental Asia based on changes to the ice-cover in the Barents-Kara seas.