Unprecedented rates of warming are shaping Arctic ecosystems and landscapes. Impacts in the Canadian Arctic are closely connected to accelerated permafrost thaw, coastal erosion and increasing river discharge to the coastal zone. Significant shifts in biodiversity and environments are evident today, but long-term ecosystem responses are crucial for discerning the effects of Holocene climate variability and accelerating rates of change in the 21st century. Here we explore ancient DNA records from sediment records taken in Tuktoyaktuk harbor (NWT), and additional sites in front of the wider Mackenzie Delta. We applied plant and animal metabarcoding, together with shotgun metagenomics. The 4500-year harbor record reflects the region’s terrestrial and marine biodiversity at multi-decadal resolution, with distinct community shifts in particular in response to sea level rise. The identification of woolly mammoth DNA in surface sediments suggests reworking of formerly buried material from mainland permafrost into coastal sediments. We hypothesize that ‘modern’ signals of extinct megafauna may act as a proxy for accelerated permafrost thaw in response to recent warming. Our study offers new perspectives on Arctic ecosystem sensitivity to climate change across the land-sea interface, and a framework for the interpretation of sedimentary ancient DNA in a rapidly warming Arctic landscape.