To reconstruct the timing and underlying forcing of major shifts in the composition of terrestrial ecosystems in arid Central Asia during the late Cenozoic (past ~7 Ma), we carry out palynological analysis of lake sediments from the Qaidam Basin (NE Tibetan Plateau, China). Our results show that the steppe/semi-desert biomes dominating the Qaidam Basin experienced marked turnovers at ~3.6 and 3.3 Ma. Most notably, the younger of these turnover events is characterized by a two- to three-fold expansion of Artemisia at the expense of other steppe/semi-desert taxa. This turnover event led to the replacement of the Ephedraceae/Chenopodiaceae-dominated and Nitraria-rich steppe/semi-deserts that were dominant in the Qaidam Basin during the Paleogene and abundant during the Miocene by Artemisia/Chenopodiaceae-dominated steppe/semi-deserts as they exist until today. The vegetation turnover events are synchronous with shifts towards drier conditions in Central Asia as documented in climate records from the Chinese Loess Plateau and the Central North Pacific Ocean. On a global scale, they can be correlated to early glaciation events in the Northern Hemisphere during the Pliocene. Integration of our palynological data from the Qaidam Basin with Northern Hemisphere climate-proxy and regional-scale tectonic information suggests that the uplift of the Tibetan Plateau posed ecological pressure on Central Asian plant communities, which made them susceptible to the effects of early Northern Hemisphere glaciations during the late Pliocene. Although these glaciations were relatively small in comparison to their Pleistocene counterparts, the transition towards drier/colder conditions pushed previously existing plant communities beyond their tolerance limits, thereby causing a fundamental reorganization of arid ecosystems. The Artemisia dominance since ~3.3 Ma resulting from this reorganization marks a point in time after which the Artemisia/Chenopodiaceae pollen ratio can serve as a reliable indicator for moisture availability in Central Asia.