The Northeast Greenland Ice Stream (NEGIS) is the main artery for ice discharge from the northeast sector of the Greenland Ice Sheet (GrIS) to the North Atlantic. Understanding the past, present and future stability of the NEGIS with respect to atmospheric and oceanic forcing is of global importance as it drains around 17% of the GrIS and has a sea-level equivalent of 1.6 m. This paper reconstructs the deglacial and Holocene history of Nioghalvfjerdsbræ (or 79N Glacier); a major outlet of the NEGIS. At high elevation (>900 m asl) autochthonous blockfield, a lack of glacially moulded bedrock and pre LGM exposure ages point to a complex exposure/burial history extending back over half a million years. However, post Marine Isotope Stage 12, enhanced glacial erosion led to fjord incision and plateaux abandonment. Between 900 and 600 m asl the terrain is largely unmodified by glacial scour but post LGM erratics indicate the advection of cold-based ice through the fjord. In contrast, below ∼600 m asl Nioghalvfjerdsfjorden exhibits a geomorphological signal indicative of a warm-based ice stream operating during the last glacial cycle. Dated ice marginal landforms and terrain along the fjord walls show initial thinning rates were slow between ∼23 and 10 ka, but post-10 ka it is evident that Nioghalvfjerdsfjorden deglaciated extremely quickly with complete fjord deglaciation below ∼500 m asl between 10.0 and 8.5 ka. Both increasing air and ocean temperatures were pivotal in driving surface lowering and submarine melt during deglaciation, but the final withdrawal of ice through Nioghalvfjerdsfjorden was facilitated by the action of marine ice sheet instability. Our estimates show that thinning and retreat rates reached a maximum of 5.29 ma−1 and 613 ma−1, respectively, as the ice margin withdrew westwards. This would place the Early Holocene disintegration of this outlet of the NEGIS at the upper bounds of contemporary thinning and retreat rates seen both in Greenland and Antarctica. Combined with recent evidence of ice stream shutdown during the Holocene, as well as predictions of changing ice flow dynamics within downstream sections of the NEGIS catchment, this suggests that significant re-organisation of the terminal zone of the ice stream is imminent over the next century.