Oscillatory climatic modes over the North Atlantic, Ethiopian Plateau, and eastern Mediterranean were examined in instrumental and proxy records from these regions. Aside from the well-known North Atlantic Oscillation (NAO) index and the Nile River water-level records, the authors study for the first time an instrumental rainfall record from Jerusalem and a tree-ring record from the Golan Heights. The teleconnections between the regions were studied in terms of synchronization of chaotic oscillators. Standard methods for studying synchronization among such oscillators are modified by combining them with advanced spectral methods, including singular spectrum analysis. The resulting cross-spectral analysis quantifies the strength of the coupling together with the degree of synchronization. A prominent oscillatory mode with a 7–8-yr period is present in all the climatic indices studied here and is completely synchronized with the North Atlantic Oscillation. An energy analysis of the synchronization raises the possibility that this mode originates in the North Atlantic. Evidence is discussed for this mode being induced by the 7–8-yr oscillation in the position of the Gulf Stream front. A mechanism for the teleconnections between the North Atlantic, Ethiopian Plateau, and eastern Mediterranean is proposed, and implications for interannual-to-decadal climate prediction are discussed.