Most existing tectonic models suggest Pliocene–Quaternary deformation and uplift of the NE Tibetan Plateau in response to the collision of India with Asia. Within the NE Tibetan Plateau, growth of the terranes was suggested to progress northeastward with the Yumu Shan (mountain) at the northeasternmost corner of the Qilian Shan (mountains) being uplifted only since about 1 Ma ago. Here we present a detailed palaeomagnetic dating and tectonosedimentological measurement of Cenozoic sediments in the eastern Jiuquan Basin related to the deformation and uplift of the North Qilian Shan and Yumu Shan. The results show that the eastern Jiuquan Basin is a Cenozoic foreland basin and received sediments at about 27.8 Ma at the latest. Eight subsequent tectonic events at about 27.8, 24.6, 13.7–13, 9.8–9.6, 5.1–3.6, 2.8–2.6, 0.8 and 0.1 Ma demonstrate the development of the foreland basin in response to Oligocene–Quaternary uplift of the North Qilian Shan and subsequent propagation of thrust–fold system owing to collision of India with Asia. The Yumu Shan is the late phase of deformation front in the thrust–fold system and commenced rapid uplift at about 9.8–9.6 Ma at the latest. A rigid block-floating model is proposed to interpret the mechanism of this deformation and uplift history.