Understanding the relative contributions of historical and anthropogenic factors to declines in genetic diversity is important for informing conservation action. Using genome-wide DNA of fresh and historic specimens, including that of two species widely thought to be extinct, we investigated fluctuations in genetic diversity and present the first complete phylogenomic tree for all nine species of the threatened shorebird genus Numenius, known as whimbrels and curlews. Most species faced sharp declines in effective population size, a proxy for genetic diversity, soon after the Last Glacial Maximum (around 20,000 years ago). These declines occurred prior to the Anthropocene and in spite of an increase in the breeding area predicted by environmental niche modeling, suggesting that they were not caused by climatic or recent anthropogenic factors. Crucially, these genetic diversity declines coincide with mass extinctions of mammalian megafauna in the Northern Hemisphere. Among other factors, the demise of ecosystem-engineering megafauna which maintained open habitats may have been detrimental for grassland and tundra-breeding Numenius shorebirds. Our work suggests that the impact of historical factors such as megafaunal extinction may have had wider repercussions on present-day population dynamics of open habitat biota than previously appreciated.