Paleoenvironmental proxy data for ocean properties, eolian sediment input, and continental rainfall based on high-resolution analyses of sediment cores from the southwestern Black Sea and the northernmost Gulf of Aqaba were used to infer hydroclimatic changes in northern Anatolia and the northern Red Sea region during the last ~7500 years. Pronounced and coherent multicentennial variations in these records reveal patterns that strongly resemble modern temperature and rainfall anomalies related to the Arctic Oscillation/North Atlantic Oscillation (AO/NAO). These patterns suggest a prominent role of AO/NAO--like atmospheric variability during the Holocene beyond interannual to interdecadal timescales, most likely originating from solar output changes.