Changes in the location of Northern Hemisphere storm tracks may cause significant societal and economic impacts under future climate change, but projections of future changes are highly uncertain and drivers of long-term changes are poorly understood. Here we develop a late Holocene storminess reconstruction from northwest Spain and combine this with an equivalent record from the Outer Hebrides, Scotland, to measure changes in the dominant latitudinal position of the storm track. The north-south index shows that storm tracks moved from a southern position to higher latitudes over the past 4000 yr, likely driven by a change from meridional to zonal atmospheric circulation, associated with a negative to positive North Atlantic Oscillation shift. We suggest that gradual polar cooling (caused by decreasing solar insolation in summer and amplified by sea-ice feedbacks) and mid-latitude warming (caused by increasing winter insolation) drove a steepening of the winter latitudinal temperature gradient through the late Holocene, resulting in the observed change to a more northern winter storm track. Our findings provide paleoclimate support for observational and modeling studies that link changes in the latitudinal temperature gradient and sea-ice extent to the strength and shape of the circumpolar vortex. Together this evidence now suggests that North Atlantic winter storm tracks may shift southward under future warming as sea-ice extent decreases and the mid- to high-latitude temperature gradient decreases, with storms increasingly affecting southern Europe.