Determining the millennial-scale behaviour of marine-based sectors of the West Antarctic Ice Sheet (WAIS) is critical to improve predictions of the future contribution of Antarctica to sea level rise. Here high-resolution ice sheet modelling was combined with new terrestrial geological constraints (in situ14C and 10Be analysis) to reconstruct the evolution of two major ice streams entering the Weddell Sea over 20 000 years. The results demonstrate how marked differences in ice flux at the marine margin of the expanded Antarctic ice sheet led to a major reorganization of ice streams in the Weddell Sea during the last deglaciation, resulting in the eastward migration of the Institute Ice Stream, triggering a significant regional change in ice sheet mass balance during the early to mid Holocene. The findings highlight how spatial variability in ice flow can cause marked changes in the pattern, flux and flow direction of ice streams on millennial timescales in this marine ice sheet setting. Given that this sector of the WAIS is assumed to be sensitive to ocean-forced instability and may be influenced by predicted twenty-first century ocean warming, our ability to model and predict abrupt and extensive ice stream diversions is key to a realistic assessment of future ice sheet sensitivity.