Monthly evaporation data for 1958-2010 from the Woods Hole Oceanographic Institution dataset are used to investigate interdecadal changes in interannual variability of Mediterranean evaporation and its links to regional climate. Analysis performed for the two climate periods characterized by the downward (1958-1978) and upward (1979-2010) trends of evaporation revealed significant season-dependent interdecadal changes in its interannual variability. The largest changes in interannual variability have been revealed during autumn when the leading empirical orthogonal functions (EOFs) are characterized by a zonal dipole pattern (except in November 1979-2010). During winter and spring, the EOF-1 and EOF-2 are characterized, respectively, by a monopole pattern and a zonal dipole and are associated with the East Atlantic (EA) and the East Atlantic-West Russia (EAWR) teleconnections. It is shown that interdecadal changes in interannual variability of Mediterranean evaporation during cold season were determined by the EA transition from the strongly negative to more neutral phase that occurred in late 1970s. Seasonally dependent changes in the structure of the leading evaporation EOFs reflect changing roles of the EA and EAWR which impact near surface air temperature, specific humidity and wind.