Floods comprise a dominant hydroclimatic phenomenon in aridlands with significant implications for humans, infrastructure, and landscape evolution worldwide. The study of short-term hydroclimatic variability, such as floods, and its forecasting for episodes of changing climate therefore poses a dominant challenge for the scientific community, and predominantly relies on modeling. Testing the capabilities of climate models to properly describe past and forecast future short-term hydroclimatic phenomena such as floods requires verification against suitable geological archives. However, determining flood frequency during changing climate is rarely achieved, because modern and paleoflood records, especially in arid regions, are often too short or discontinuous. Thus, coeval independent climate reconstructions and paleoflood records are required to further understand the impact of climate change on flood generation. Dead Sea lake levels reflect the mean centennial-millennial hydrological budget in the eastern Mediterranean. In contrast, floods in the large watersheds draining directly into the Dead Sea, are linked to short-term synoptic circulation patterns reflecting hydroclimatic variability. These two very different records are combined in this study to resolve flood frequency during opposing mean climates. Two 700-year-long, seasonally-resolved flood time series constructed from late Pleistocene Dead Sea varved sediments, coeval with significant Dead Sea lake level variations are reported. These series demonstrate that episodes of rising lake levels are characterized by higher frequency of floods, shorter intervals between years of multiple floods, and asignificantly larger number of years that experienced multiple floods. In addition, floods cluster into intervals of intense flooding, characterized by 75% and 20% increased frequency above their respective background frequencies during rising and falling lake-levels, respectively. Mean centennial precipitation in the eastern Mediterranean is therefore coupled with drastic changes in flood frequencies. These drastic changes in flood frequencies are linked to changes in the track, depth, and frequency of mid-latitude eastern Mediterranean cyclones, determining mean climatology resulting in wetter and drier regional climatic episodes.