Despite the multiple impacts of mineral aerosols on global and regional climate and the primary climatic control on atmospheric dust fluxes, dust-climate feedbacks remain poorly constrained, particularly at submillennial time scales, hampering regional and global climate models. We reconstruct Saharan dust fluxes over Western Europe for the last 5000 years, by means of speleothem strontium isotope ratios (87Sr/86Sr) and karst modeling. The record reveals a long-term increase in Saharan dust flux, consistent with progressive North Africa aridification and strengthening of Northern Hemisphere latitudinal climatic gradients. On shorter, centennial to millennial scales, it shows broad variations in dust fluxes, in tune with North Atlantic ocean-atmosphere patterns and with monsoonal variability. Dust fluxes rapidly increase before (and peaks at) Late Holocene multidecadal- to century-scale cold climate events, including those around 4200, 2800, and 1500 years before present, suggesting the operation of previously unknown strong dust-climate negative feedbacks preceding these episodes.