The cheetah (Acinonyx jubatus) has been described as a species with low levels of genetic variation. This has been suggested to be the consequence of a demographic bottleneck 10 000–12 000 years ago (ya) and also led to the assumption that only small genetic differences exist between the described subspecies. However, analysing mitochondrial DNA and microsatellites in cheetah samples from most of the historic range of the species we found relatively deep phylogeographic breaks between some of the investigated populations, and most of the methods assessed divergence time estimates predating the postulated bottleneck. Mitochondrial DNA monophyly and overall levels of genetic differentiation support the distinctiveness of Northern-East African cheetahs (Acinonyx jubatus soemmeringii). Moreover, combining archaeozoological and contemporary samples, we show that Asiatic cheetahs (Acinonyx jubatus venaticus) are unambiguously separated from African subspecies. Divergence time estimates from mitochondrial and nuclear data place the split between Asiatic and Southern African cheetahs (Acinonyx jubatus jubatus) at 32 000–67 000 ya using an average mammalian microsatellite mutation rate and at 4700–44 000 ya employing human microsatellite mutation rates. Cheetahs are vulnerable to extinction globally and critically endangered in their Asiatic range, where the last 70–110 individuals survive only in Iran. We demonstrate that these extant Iranian cheetahs are an autochthonous monophyletic population and the last representatives of the Asiatic subspecies A. j. venaticus. We advocate that conservation strategies should consider the uncovered independent evolutionary histories of Asiatic and African cheetahs, as well as among some African subspecies. This would facilitate the dual conservation priorities of maintaining locally adapted ecotypes and genetic diversity.