The world largest alpine permafrost region, the Tibetan Plateau, will experience amplified warming under global climate change scenarios. Studying its environmental evolution in the geological past is crucial to further our understanding of mechanism and thresholds of climate change. Here we present a 3.5-million-year-long, high-altitude vegetation and climate record from the Kunlun Pass Basin to reconstruct the transition from the sustained warm, high carbon dioxide environment of the Pliocene to the cool glacial and interglacial periods of the Pleistocene, 4.31 to 0.85 million years (Ma) ago. The Early Pliocene pollen record indicates the occurrence of patches of broadleaved and coniferous forests in a semi-desert shrubland at this high-altitude site. Pollen derived quantitative climate estimates based on modern pollen rain transfer functions suggest a moister climate before 4.0 Ma with mean annual temperatures (MATs) > 14 °C warmer than today. The retreat of broadleaved and coniferous forests from the Kunlun Pass Basin area is linked to stepwise cooling at ~4.0 Ma and during the Plio-Pleistocene transition between 2.7 and 2.6 Ma. Pollen derived climate estimates and Δ47-palaeothermometry indicate an abrupt cooling of ~4–8 °C resulting in the onset of permafrost condition on the Tibetan Plateau after 2.7 Ma. An expansion of Chenopodioideae dominated xerophytic shrublands after 3.8 Ma and 2.15 Ma indicates a reduction in precipitation on the NE Tibetan Plateau, which appears to be linked to a weakening of the East Asian Summer Monsoon at the Plio-Pleistocene transition. The reconstructed cooling at the Kunlun Pass Basin site reflects the regional expression of global climate change with high-elevation temperature amplification hence rejecting the notion of a major tectonic uplift of the Tibetan Plateau during the Plio-Pleistocene.