Holocene climate records from the Mediterranean are marked by pervasive millennial to centennial-scale climate variability. Here, we investigate East-West Mediterranean atmospheric and oceanic teleconnections by computing phase-relationships between oxygen isotope (δ ¹⁸ O) records generated on Soreq (East) and Chorchia (West) spelaeothems, as well as between δ ¹⁸ O and carbon isotope (δ ¹³ C) records from planktonic and benthic foraminifera from core PS009PC (East, Levantin Basin), ODP Site 963D (Central, Sicily Strait), and core KESC9-14 (West, Ligurian Basin). These marine sites are all located at intermediate water depths (560–460 m depth). Hence, the benthic foraminiferal δ ¹⁸ O records reflect mainly the intermediate ocean temperature/δ ¹⁸ O of the water mass, and the benthic δ ¹³ C is a proxy for the intensity of water flowing at the studied depth called Levantine Intermediate Water (LIW). For both western and eastern cores, the planktonic stable isotopic records reflect the climate-induced activity of the nearby river system. We find broadly in-phase relationships between the spelaeothem δ ¹⁸ O records and between the planktonic δ ¹⁸ O and δ ¹³ C records at most multi-centennial and millennial periodicities. This is indicative of closely linked (hydro-) climatic conditions in Southern Europe, the Levant, and North Africa over the last 8000 years. Conversely, at intermediate water depths, we find a distinct out-of-phase relationship between the East/Central and West Mediterranean benthic δ ¹⁸ O and δ ¹³ C records at 1000–2000 years periodicities. We interpret this see-saw pattern as indicative of a persistent regional influence of LIW on oceanographic conditions in the intermediate depths of the eastern basin. Conversely, we suggest a strong influence of the modified Atlantic Ocean inflow (MAW) in the intermediate water formation in the Western Mediterranean (‘Winter Intermediate Water’; WIW). This WIW overprints, at least partially, the LIW signal that reaches the western Mediterranean causing the out-of-phase relationship between the east and the west oceanographic signals at intermediate depths.