The temporal and spatial coarseness of megafaunal fossil records complicates attempts to to disentangle the relative impacts of climate change, ecosystem restructuring, and human activities associated with the Late Quaternary extinctions. Advances in the extraction and identification of ancient DNA that was shed into the environment and preserved for millennia in sediment now provides a way to augment discontinuous palaeontological assemblages. Here, we present a 30,000-year sedimentary ancient DNA (sedaDNA) record derived from loessal permafrost silts in the Klondike region of Yukon, Canada. We observe a substantial turnover in ecosystem composition between 13,500 and 10,000 calendar years ago with the rise of woody shrubs and the disappearance of the mammoth-steppe (steppe-tundra) ecosystem. We also identify a lingering signal of Equus sp. (North American horse) and Mammuthus primigenius (woolly mammoth) at multiple sites persisting thousands of years after their supposed extinction from the fossil record.