This is the author accepted manuscript. The final version is available from the publisher via the DOI in this record. First Published on February 03, 2017 ; 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. ; Orme was funded by the University of Exeter and a British Geological Survey University Funding Initiative (BUFI) Studentship. We are grateful to the ACCROTELM (Abrupt Climate Changes Recorded over the European Land Mass) Project, supported by European Commission Contract EVK2-CT-2002–00166, for contributing the dated Pedrido Bog core.