Euro-Mediterranean climate variability has been associated mostly with the upstream atmospheric circulation and teleconnection patterns, the North Atlantic Oscillation and European blocking being the main ones. This study shows, for the first time, that the East Asian trough (EAT), a prominent circulation feature of the mid-troposphere in the downstream side, might exert a strong and significant role on the interannual variability of the Euro-Mediterranean climate during boreal winters. We performed empirical orthogonal function analysis on the regions of the EAT and Mediterranean trough (MedT), an important system modulating the climate of the region, to obtain the respective dominant modes of variability at 500-hPa geopotential heights. It appears that the leading modes, the intensity in the case of the EAT and the zonal displacement in the case of the MedT, are significantly correlated with each other (r=-0.64, p<0.001). Consequently, when the EAT is strong (weak), the MedT is observed in the west (east) of its climatological location resulting in a warmer (cooler) Middle East and northeastern Africa, a cooler (warmer) western Europe and northwestern Africa, and wetter (dryer) Italian, Balkan and Anatolian peninsulas. Given the fact that the EAT is also a key determinant of the East Asian winter climate, the identified mid-tropospheric link between East Asia and Mediterranean could help interpret some temperature and precipitation co-variability on the opposite sides of the Eurasian continent. We suggest that studies involving the Euro-Mediterranean climate should also consider the role of the EAT as it seems to be a potential driver of the year-to-year, perhaps longer-term, climate variability in the region.