Apatite fission-track and vitrinite-reflectance data from Phanerozoic rocks of the northern Qilian Shan and Jiuxi basin, at the northeastern margin of the Tibetan Plateau, show a complex thermal history with multiple paleothermal events. Peak paleotemperatures, reached in the middle Cretaceous, suggest that hydrocarbon generation occurred in the basin at that time. Paleozoic-Mesozoic samples show evidence of a middle Tertiary cooling episode between 20 and 10 Ma. This thermal fingerprint is significant because stratigraphic evidence for Miocene exhumation is overwhelmed by spectacular Pliocene-Pleistocene deformation and erosion. We interpret the Miocene cooling as recording initial exhumation of the northern Qilian Shan—earlier than other models have proposed (i.e., after 6– 5 Ma). Miocene cooling is broadly coincident with Cenozoic uplift and exhumation recorded elsewhere in the Tibetan-Tarim region.