Storm surges, leading to catastrophic coastal flooding, are amongst the most feared natural hazards due to the high population densities and economic importance of littoral areas. Using the Central Mediterranean Sea as a model system, we provide strong evidence for enhanced periods of storminess leading to coastal flooding during the last 4500 years. We show that long-term correlations can be drawn between storminess and solar activity, acting on cycles of around 2200-yr and 230-yr.