The growth history of the Tibetan Plateau provides a valuable natural laboratory to understand tectonic processes of the India-Asia collision and their impact on and interactions with Asian and global climate change. However, both Tibetan Plateau growth and Asian paleoenvironments are generally poorly documented in pre-Pliocene times and reflect limited temporal coverage for different parts of the plateau. Here we present magnetostratigraphic results from the Xining Basin, at the NE margin of the Tibetan Plateau, precisely dating the record between the earliest Oligocene (similar to 33 Ma) to the middle Miocene (similar to 16 Ma). The pattern of observed paleomagnetic polarity zones is unequivocally correlated to the geomagnetic polarity time scale (GPTS) indicating relatively constant and low sediment accumulation rates (32 m/Myr) except for a peculiar period of unstable accumulation between 25.3 and 19.7 Ma. At the beginning of this interval, a marked permanent increase in magnetite content of the sediments is observed and likely relates to a change in provenance. We directly relate this unstable period of sediment accumulation and provenance change to the coeval exhumation recently reported by low-temperature thermochronology from the Laji Shan range, which subsequently formed the southern margin of the Xining Basin. Evidence for NE Tibet tectonism at 25-20 Ma can be associated with widespread deformation over the entire Himalayan-Tibetan orogen at this time, which may be linked to the coeval appearance of monsoon climate in Eastern Asia and the onset of central Asian desertification.