Causes of late Quaternary extinctions of large mammals ("megafauna") continue to be debated, especially for continental losses, because spatial and temporal patterns of extinction are poorly known. Accurate latest appearance dates (LADs) for such taxa are critical for interpreting the process of extinction. The extinction of woolly mammoth and horse in northwestern North America is currently placed at 15,000-13,000 calendar years before present (yr BP), based on LADs from dating surveys of macrofossils (bones and teeth). Advantages of using macrofossils to estimate when a species became extinct are offset, however, by the improbability of finding and dating the remains of the last-surviving members of populations that were restricted in numbers or confined to refugia. Here we report an alternative approach to detect 'ghost ranges' of dwindling populations, based on recovery of ancient DNA from perennially frozen and securely dated sediments (sedaDNA). In such contexts, sedaDNA can reveal the molecular presence of species that appear absent in the macrofossil record. We show that woolly mammoth and horse persisted in interior Alaska until at least 10,500 yr BP, several thousands of years later than indicated from macrofossil surveys. These results contradict claims that Holocene survival of mammoths in Beringia was restricted to ecologically isolated high-latitude islands. More importantly, our finding that mammoth and horse overlapped with humans for several millennia in the region where people initially entered the Americas challenges theories that megafaunal extinction occurred within centuries of human arrival or were due to an extraterrestrial impact in the late Pleistocene.