Sea level anomaly (SLA) data in the Mediterranean and Black seas obtained by ocean radar altimetry missions (TOPEX/Poseidon, Jason, ERS-1/2 and ENVISAT) are studied in conjunction with corresponding sea-surface temperature (SST) data. The studied time span is 11 years long, 1993-2003. Besides confirming previously published results, we report a significant, but enigmatic, abrupt change in the SLA trend that took place in mid-1999 which has been corroborated by independent tide gauge data. Results obtained from an Empirical Orthogonal Function (EOF) analysis show that the change in 1999 is not uniform in the Mediterranean Sea, which can thus be divided into 6 sub-regions. This 1999 kink in the rate-of-change happened in four of these sub-regions as well as in the Black Sea. Upon splitting the time series at mid-1999, we see a good spatial correlation for the first period between SLA and SST trend maps in both the Mediterranean Sea and the Black Sea, while for the second period such correlation virtually disappeared in the Mediterranean and is greatly reduced in the Black Sea. It implies that prior to 1999 the steric effect was a major factor in interannual variability of sea level in the Mediterranean and Black seas, but after the time the SLA inverted its trend in mid-1999, this steric effects became less important as a forcing factor. It is premature to draw conclusions about the physical processes involved based on the data sets we study, but it appears that the Mediterranean Sea might be seeing a restoration of Adriatic as the main source of deep water in the eastern basin, while the Black Sea level has been largely controlled by an interannual or interdecadal steric effect.