Uplift of the Tibetan Plateau and the Himalayas since the onset of the Indo-Asia collision is held responsible for Asian aridification and monsoon intensification, but may also have gradually cooled global climate, leading to the 34 Ma Eocene-Oligocene transition. To unravel the interplay between Tibetan uplift and global climate, proxy records of Asian paleoenvironments constrained by accurate age models are needed for the Paleogene Period. Here we report the 38 Ma appearance of high-altitude vegetation recovered from palynological assemblages in precisely dated lacustrine sediments from the Xining Basin of the northeastern Tibetan Plateau region. This result confirms previous evidence for important regional uplift in the central and northern Tibetan Plateau regions during the early stage of the Indo-Asia collision. This is consistent with the idea that the associated increase in rock weathering and erosion contributed to lowering of atmospheric CO2, leading to the Eocene-Oligocene transition.