The growth and deformation history of the Qilian-Nan Shan thrust belt bounding the NE Qaidam Basin figures importantly in testing models of Tibetan Plateau uplift during the India-Asia collision. However, debate exists about the onset of uplift and exhumation of the Qilian-Nan Shan, with timing estimates ranging from early Paleocene to late Miocene. Here we report integrated analyses of magnetostratigraphy, anisotropy of magnetic susceptibility, sediment provenance, and paleoclimate (using environmental magnetic parameters) for Cenozoic fluvio-lacustrine strata from the Dahonggou section south of the Qilian-Nan Shan. The results are interpreted to demonstrate an early Miocene (ca. 20 Ma) onset of sediment accumulation in this location, with clastic sediment derived initially from the southern Qimen Tagh highland. The sediment source then switched to the northern part of the Qilian Shan region after ca. 18.5 Ma, consistent with initial uplift and exhumation of the Qilian Shan. Thereafter, two additional provenance shifts reveal progressive southward propagation of deformation in the Qilian-Nan Shan. As a result of this southward growth of Qilian-Nan Shan topography, precipitation increased after ca. 11 Ma at the study site due to orographic interception of moisture from the south. This work improves our understanding of the depositional age, sediment provenance, and paleoclimate history of the Qaidam Basin and reveals a prolonged history of Qilian-Nan Shan deformation and uplift, which may have accelerated during the late Miocene.