Abstract: Utilizing the NCEP, JRA-55, and ERA5 reanalysis data sets spanning from the boreal winters from 1958/1959 to 2020/2021, this study investigates atmospheric teleconnection patterns that affect winter air temperature variations in East Asia. After removing the linear trend, we explore the primary modes of these temperature variations and their interdecadal variations using conventional statistical methods, e.g., Empirical Orthogonal Function (EOF), Rotated Empirical Orthogonal Function (REOF), correlation, and partial regression analyses. The results show that the Scandinavian teleconnection (SCA) and the East Atlantic (EA) teleconnection patterns significantly influence the first and second principal components (PC1 and PC2, respectively) of winter air temperature variability in East Asia. On interdecadal timescales, these patterns show consistent shifts. Specifically, changes in the SCA patterns during the late 1970s and early 2000s align well with shifts in PC1 of East Asian air temperatures. Similarly, the EA pattern’s phase shifts in the early 1980s, late 1990s, and early 2010s correspond to changes in PC2. Notably, the correlation coefficients between the SCA index and PC1 (R1) and between the EA index and PC2 (R2) reveal different decadal variations, diverging from those of the two teleconnections. Before the mid-1980s, R1 shows a decreasing trend, followed by a significant increase, indicating a strengthening influence of the SCA on East Asian air temperature. Such an interdecadal variation in R1 strength is related to circulation anomalies centered over western Russia associated with SCA, extending further eastward, possibly determined by the Atlantic Multidecadal Oscillation (AMO). There is also an evident decadal variation in R2 strength. R2 is strong only during the 1970s to 1980s and after the 2000s. This suggests that the EA’s influence on East Asian air temperatures relies on its ability to form a local meridional dipole circulation pattern rather than being directly related to sea surface temperature or sea ice concentration anomalies.