The phylogeography of western Palearctic species is relatively well studied, but data on Eastern Central Asia are scarce. We present one of the first data sets from a widespread terrestrial vertebrate (Bufo pewzowi) inhabiting Eastern Central Asian mountains and deserts to gain knowledge on its phylogeography in this region. We applied combined phylogenetic and demographic analyses to understand the evolutionary history using mitochondrial DNA D-loop variation of toads from 37 locations. Genetic structure of Bufo pewzowi is strongly affected by landscape: we found three haplotype groups in eastern Kazakhstan, Dzungaria and Tarim Basin, divided by the Tian Shan and Dzungarian Alatau ranges. A vicariant hypothesis may explain divergence among groups. The divergence time of the three major clades was estimated about 0.9 million years ago (confidence interval 0.5-1.4), and is discussed with respect to Quaternary uplifting and glaciation in the Tian Shan. Demographic analyses provided evidence for both historical bottlenecks and population expansions and suggested Pleistocene signatures. Glacial refugia were inferred in the Tarim Basin (around the Turpan depression), in southern Dzungaria (Urumqui region), at the northern foot of the Tian Shan (Gongnaisi) and perhaps at the Altai range (Terekti). Regional Post-Last Glacial Maximum dispersal patterns are proposed. A taxonomic hypothesis is presented. This study provides a detailed history of how a widespread terrestrial vertebrate responded to geological change and Quaternary glacial events in Eastern Central Asia and may have significance for future phylogeographic research in this understudied region.