The Late Paleogene surface height and paleoenvironment for the core area of the Qinghai-Tibetan Plateau (QTP) remain critically unresolved. Here, we report the discovery of the youngest well-preserved fossil palm leaves from Tibet. They were recovered from the Late Paleogene (Chattian), ca. 25.5 ± 0.5 million years, paleolake sediments within the Lunpola Basin (32.033°N, 89.767°E), central QTP at a present elevation of 4655 m. The anatomy of palms renders them intrinsically susceptible to freezing, imposing upper bounds on their latitudinal and altitudinal distribution. Combined with model-determined paleoterrestrial lapse rates, this shows that a high plateau cannot have existed in the core of Tibet in the Paleogene. Instead, a deep paleovalley, whose floor was <2.3 km above mean sea level bounded by (>4 km) high mountain systems, formed a topographically highly varied landscape. This finding challenges prevailing views on tectonic processes, monsoon dynamics, and the evolution of Asian biodiversity.