Background: The effects of historical geology and climatic events on the evolution of plants around the Qinghai-Tibetan Plateau region have been at the center of debate for years. To identify the influence of the uplift of the Tianshan Mountains and/or climatic oscillations on the evolution of plants in arid northwest China, we investigated the phylogeography of the Euphrates poplar (Populus euphratica) using chloroplast DNA (cpDNA) sequences and nuclear microsatellites, and estimated its historical distribution using Ecological Niche Modeling (ENM). Results: We found that the Euphrates poplar differed from another desert poplar, P. pruinosa, in both nuclear and chloroplast DNA. The low clonal diversity in both populations reflected the low regeneration rate by seed/seedlings in many locations. Both cpDNA and nuclear markers demonstrated a clear divergence between the Euphrates poplar populations from northern and southern Xinjiang regions. The divergence time was estimated to be early Pleistocene based on cpDNA, and late Pleistocene using an Approximate Bayesian Computation analysis based on microsatellites. Estimated gene flow was low between these two regions, and the limited gene flow occurred mainly via dispersal from eastern regions. ENM analysis supported a wider distribution of the Euphrates poplar at 3 Ma, but a more constricted distribution during both the glacial period and the interglacial period. Conclusions: These results indicate that the deformation of the Tianshan Mountains has impeded gene flow of the Euphrates poplar populations from northern and southern Xinjiang, and the distribution constriction due to climatic oscillations further accelerated the divergence of populations from these regions. To protect the desert poplars, more effort is needed to encourage seed germination and seedling establishment, and to conserve endemic gene resources in the northern Xinjiang region.