El Nino-Southern Oscillation (ENSO) teleconnections over Europe and the Middle East are evaluated using an oxygen isotope coral time series from the northern Red Sea and various instrumental data sets. We detect a shift in the correlation between the Nino3 index and the Red Sea coral record in 1970s and we show that this shift can be attributed to non-stationary circulation regimes and related ENSO teleconnections. We find that positive anomalies of oxygen isotope in the Red Sea coral record from mid-1930s to late 1960s are associated with a strong Pacific-North Atlantic teleconnection accompanied by a weak Aleutian Low, a more zonal flow at mid-latitudes, and La Nina conditions in tropical Pacific. In contrast, positive anomalous of oxygen isotopes in the Red Sea coral after 1970s are related to El Nino conditions and weaker Pan-Pacific-Atlantic circulation regimes. Using the window correlation of the northern Red Sea coral record with two coral records from the tropical and subtropical Pacific, we find non-stationary relationships between the tropical Pacific and the European/Middle Eastern climate during the pre-instrumental period. Our results imply that the modulation of teleconnections at interdecadal time scales provides a limitation in the prediction and reconstruction of remote climate phenomena such as the ENSO impact over Europe.