The area and elevation of the Tibetan Plateau over time has directly affected Asia’s topography, the characteristics of the Asian monsoon, and modified global climate, but in ways that are poorly understood. Charting the uplift history is crucial for understanding the mechanisms that link elevation and climate irrespective of time and place. While some palaeoelevation data are available for southern and central Tibet, clues to the uplift history of northern Tibet remain sparse and largely circumstantial. Leaf fossils are extremely rare in Tibet but here we report a newly discovered early Miocene barberry (Berberis) from Wudaoliang in the Hoh-Xil Basin in northern Tibet, at a present altitude of 4611 ± 9 m. Considering the fossil and its nearest living species probably occupied a similar or identical environmental niche, the palaeoelevation of the fossil locality, corrected for Miocene global temperature difference, is estimated to have been between 1395 and 2931 m, which means this basin has been uplifted ~2–3 km in the last 17 million years. Our findings contradict hypotheses that suggest northern Tibet had reached or exceeded its present elevation prior to the Miocene.