Millennial- and multi-centennial scale climate variability during the Holocene has been well documented, but its impact on the distribution and timing of extreme river floods has yet to be established. Here we present a meta-analysis of more than 2000 radiometrically dated flood units to reconstruct centennial-scale Holocene flood episodes in Europe and North Africa. Our data analysis shows a general increase in flood frequency after 5000 cal. yr BP consistent with a weakening in zonal circulation over the second half of the Holocene, and with an increase in winter insolation. Multi-centennial length phases of flooding in UK and central Europe correspond with periods of minimum solar irradiance, with a clear trend of increasing flood frequency over the last 1000 years. Western Mediterranean regions show synchrony of flood episodes associated with negative phases of the North Atlantic Oscillation that are out-of-phase with those evident within the eastern Mediterranean. This long-term flood record reveals complex but geographically highly interconnected climate-flood relationships, and provides a new framework to understand likely future spatial changes of flood frequency.