The surface temperature variance and its potential change with global warming are most prominent in winter over Northern Hemisphere mid-high latitudes. Consistent wintertime surface temperature variability has been observed over large areas in Eurasia and North America on a broad range of time scales. However, it remains a challenge to quantify where and how the coherent change of temperature anomalies occur over the two continents. Here we demonstrate the coherent change of wintertime surface temperature anomalies over North Asia and the central-eastern parts of North America for the period from 1951 to 2015. This is supported by the results from the empirical orthogonal function analysis of surface temperature and temperature trend anomalies over the Northern Hemisphere extratropical lands and the timeseries analysis of the regional averaged temperature anomalies over North Asia and the Great Plains and Great Lakes. The Asian-Bering-North American (ABNA) teleconnection provides a pathway to connect the regional temperature anomalies over the two continents. The ABNA is also responsible for the decadal variation of the temperature relationship between North Asia and North America.