Background: The evolutionary origin and historical demography of extant Arcto-Tertiary forest species in East Asia is still poorly understood. Here, we reconstructed the evolutionary and population demographic history of the two extant Euptelea species in China (E. pleiosperma) and Japan (E. polyandra). Chloroplast/nuclear DNA sequences and microsatellite loci were obtained from 36 Euptelea populations to explore molecular structure and diversity in relation to past and present distributions based on ecological niche modelling (ENM). Time-calibrated phylogenetic/phylogeographic inferences and niche-identity tests were used to infer the historical process of lineage formation. Results: Euptelea pleiosperma diverged from E. polyandra around the Late Miocene and experienced significant ecological differentiation. A near-simultaneous diversification of six phylogroups occurred during the mid-to-late Pliocene, in response to the abrupt uplift of the eastern Tibetan Plateau and an increasingly cooler and drier climate. Populations of E. pleiosperma seem to have been mostly stationary through the last glacial cycles, while those of E. polyandra reflect more recent climate-induced cycles of range contraction and expansion. Conclusions: Our results illustrate how Late Neogene climatic/tectonic changes promoted speciation and lineage diversification in East Asias Tertiary relict flora. They also demonstrate for the first time a greater variation in such species responses to glacial cycles in Japan when compared to congeners in China.