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. Comparison of correlations between the heat fluxes and the intensity and location of the Azores High (AH), and the NAO and East Atlantic-West Russia (EAWR) teleconnections, along with analysis of composites of surface temperature, humidity and wind fields for different teleconnection states, demonstrates that variations of the AH are found to explain the heat flux changes more successfully than the NAO and the EAWR. Trends in sea level pressure and longitude of the Azores High during DJF show a strengthening, and an eastward shift. DJF Azores High pressure and longitude are shown to co-vary such that variability of the Azores High occurs 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 Azores High 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 Mediterranean Sea sensible and latent heat fluxes.