Interannual variations of latent heat fluxes (LHF) and sensible heat fluxes (SHF) over the Mediterranean for the boreal winter season (DJF) show positive trends during 1958–2011. Using reanalysis and satellite-based products, the variability and trends in the heat fluxes are compared with variations in three atmospheric teleconnection patterns: the North Atlantic Oscillation (NAO), the pressure and position of the Azores High (AH), and the East Atlantic-West Russia teleconnection pattern (EAWR). Comparison of correlations between the heat fluxes and teleconnections, along with analysis of composites of surface temperature, humidity, and wind fields for different teleconnection states, demonstrates that the AH explains the heat flux changes more successfully than NAO and EAWR. Trends in pressure and longitude of the Azores High show a strengthening and an eastward shift. Variations of the Azores High occur along an axis defined by lower pressure and westward location at one extreme and higher pressure and eastward location at the other extreme. The shift of the AH from predominance of the low/west state to the high/east state induces trends in Mediterranean Sea surface winds, temperature, and moisture. These, combined with sea surface warming trends, produce trends in wintertime sensible and latent heat fluxes.