Unravelling prehistoric anthropogenic impacts on biodiversity represents a key challenge for biologists and archaeologists. New Zealand's endemic Stewart Island Shag (Leucocarbo chalconotus) comprises two distinct phylogeographic lineages, currently restricted to the country's south and southeast. However, fossil and archaeological remains suggest a far more widespread distribution at the time of Polynesian settlement ca. 1280 AD, encompassing much of coastal South Island. We used modern and ancient DNA, radiocarbon dating, and Bayesian modelling, to assess the impacts of human arrival on this taxon. Our analyses show that the southeast South Island (Otago) lineage was formerly widespread across coastal South Island, but experienced dramatic population extinctions, range retraction and lineage loss soon after human arrival. By comparison, the southernmost (Foveaux Strait) lineage has experienced a relatively stable demographic and biogeographic history since human arrival, retaining much of its mitochondrial diversity. Archaeological data suggest that these contrasting demographic histories (retraction vs. stability) reflect differential human impacts in mainland South Island vs. Foveaux Strait, highlighting the importance of testing for temporal and spatial variation in human-driven faunal declines.