Reliable knowledge of ice discharge dynamics for the Greenland Ice Sheet via its ice streams is essential if we are to understand its stability under future climate scenarios. Little however is known about the paleo ice-sheet configuration in areas still covered by ice. Here we use radio-echo sounding data to decipher the regional deformation history of the north-eastern Greenland Ice Sheet from its internal stratigraphy. We map folds deep below the surface that we attribute to the activity of a now-extinct ice stream, which shows strong similarities to the Northeast Greenland Ice Stream. We propose that locally this ancient ice flow regime reached much further inland than today’s and was ceased in the Holocene. The new insight that major ice streams may abruptly disappear will affect future approaches to understanding and modelling the response of Earth’s ice sheets to global warming.