Prior to the Holocene, the range of the saiga antelope (Saiga tatarica) spanned from France to the Northwest Territories of Canada. Although its distribution subsequently contracted to the steppes of Central Asia, historical records indicate that it remained extremely abundant until the end of the Soviet Union, after which its populations were reduced by over 95%. We have analysed the mitochondrial control region sequence variation of 27 ancient and 38 modern specimens, to assay how the species' genetic diversity has changed since the Pleistocene. Phylogenetic analyses reveal the existence of two well-supported, and clearly distinct, clades of saiga. The first, spanning a time range from >49,500 (14) C ybp to the present, comprises all the modern specimens and ancient samples from the Northern Urals, Middle Urals and Northeast Yakutia. The second clade is exclusive to the Northern Urals and includes samples dating from between 40,400 to 10,250 (14) C ybp. Current genetic diversity is much lower than that present during the Pleistocene, an observation that data modelling using serial coalescent indicates cannot be explained by genetic drift in a population of constant size. Approximate Bayesian Computation analyses show the observed data is more compatible with a drastic population size reduction (c. 66-77%) following either a demographic bottleneck in the course of the Holocene or late Pleistocene, or a geographic fragmentation (followed by local extinction of one subpopulation) at the Holocene/Pleistocene transition.