The intricate interplay between subglacial topography and ice-sheet dynamics is key to the evolution of large ice sheets, but in Greenland as elsewhere the effects of long-term glacial history on landscape evolution remain poorly constrained. Here we measure abundances of cosmogenic 10Be and 26Al in bedrock and transported boulders to unveil the glaciation and erosion history of Dove Bugt, northeast Greenland. In agreement with studies of west Greenland, we find that apparent exposure ages increase with elevation from 9 ka to 13 ka in low-lying valleys to 21 ka to 204 ka on high-elevation, blockfield-covered plateaus. We employ a Markov chain Monte Carlo inversion framework to constrain the probability of various erosion histories, and we quantify the residence time of samples within the upper 2 m of the bedrock subsurface—a measure defined as the cosmogenic nuclide memory. This cosmogenic nuclide memory exceeds 600 ka on the highest plateaus but is limited to less than 500 ka in most other high-elevation samples and to less than 100 ka at low-elevations. Our results define maximum limits for the fraction of ice cover during the past 1 Ma to ∼70% on the Store Koldewey peaks and ∼90% farther inland at Pusterdal, respectively. Minimum limits to ice cover, however, cannot be reliably constrained by the data. Finally, we propose that limited erosion on the highest plateaus of Store Koldewey since 0.6–1.0 Ma indicates a minimum age for fjord-plateau formation within this area of northeast Greenland.