<jats:title>Abstract</jats:title> <jats:p>El Niño–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 datasets. A shift in the correlation between the Niño-3 index and the Red Sea coral record in the 1970s is detected, and it is shown that this shift can be attributed to nonstationary circulation regimes and related ENSO teleconnections. It is found that positive anomalies of oxygen isotope in the Red Sea coral record from the middle 1930s to the late 1960s are associated with a strong Pacific–North Atlantic teleconnection accompanied by a weak Aleutian low, a more zonal flow at midlatitudes, and La Niña conditions in tropical Pacific. In contrast, positive anomalies of oxygen isotopes in the Red Sea coral after the 1970s are related to El Niño 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, nonstationary relationships between the tropical Pacific and the European–Middle Eastern climate during the preinstrumental period are found. The results imply that the modulation of teleconnections at interdecadal timescales provides a limitation in the prediction and reconstruction of remote climate phenomena such as the ENSO impact over Europe.</jats:p>