Abstract: The Qilian Shan lies along the northeastern edge of the Tibetan Plateau. To constrain its deformation history, we conducted integrated research on Mesozoic–Cenozoic stratigraphic sections in the Jiuxi Basin immediately north of the mountain range. Paleocurrent measurements, sandstone compositional data, and facies analysis of Cenozoic stratigraphic sections suggest that the Jiuxi Basin received sediments from the Altyn Tagh Range in the northwest, initially in the Oligocene (~33 Ma), depositing the Huoshaogou Formation in the northern part of the basin. Later, the source area of the Jiuxi Basin changed to the Qilian Shan in the south during Late Oligocene (~27 Ma), which led to the deposition of the Baiyanghe Formation. We suggest that uplift of the northern Qilian Shan induced by thrusting began no later than the Late Oligocene. Fission-track analysis of apatite from the Qilian Shan yields further information about the deformation history of the northern Qilain Shan and the Jiuxi Basin. It shows that a period of rapid cooling, interpreted as exhumation, initiated in the Oligocene. We suggest that this exhumation marked the initial uplift of the Qilian Shan resulting from the India–Asia collision.