The last deglaciation, 20,000–10,000 years ago, was a period of global warming and rapidly shrinking ice sheets. It was also climatically unstable and retreats were interrupted by re-advances. Retreat rates and timing relative to climatic changes have therefore been difficult to establish. We here study a suite of 12 marine sediment cores from Storfjorden and Storfjorden Trough, Svalbard. The purpose is to reconstruct retreat patterns and retreat rates of a high northern latitude marine-based ice stream from the Svalbard-Barents Sea Ice Sheet in relation to paleoceanographic and paleoclimatic changes. The study is based on abundance and composition of planktic and benthic foraminiferal assemblages, ice rafted debris (IRD), lithology, and 70 AMS-14C dates. For core 460, we also calculate sea surface and bottom water temperatures and bottom water salinity. The results show that retreat rates of the ice shelf and ice streams of Storfjorden Trough/Storfjorden (‘Storfjorden Ice Stream’) closely followed the deglacial atmospheric and ocean temperature changes. During the start of the Bølling interstadial retreat rates in Storfjorden Trough probably exceeded 2.5 km/year and more than 10,000 km2 of ice disappeared almost instantaneously. A similarly rapid retreat occurred at the start of the Holocene interglacial, when 4500 km2 of ice broke up. Maximum rates during the deglaciation match the fastest modern rates from Antarctica and Greenland. Correlation of data show that the ice streams in several fjords from northern Norway retreated simultaneously with the Storfjorden Ice Stream, indicating that temperature was the most important forcing factor of the Svalbard-Barents Sea Ice Sheet during the deglaciation.