To help understand the deformational history of the northeastern Tibetan Plateau, paleomagnetic samples were collected from 177 sites and two magnetostratigraphic sections at 16 localities distributed among Upper Jurassic-Lower Cretaceous to Pliocene sedimentary and subordinate volcanic rocks within the Xining-Lanzhou region (34--37¿N, 101--105¿E). A total of 127 sites at 12 localities yielded primary magnetizations confirmed by fold, reversal, and conglomerate tests. Age control on sedimentary rocks is provided by regional synthesis of chronostratigraphic data and our own biostratigraphic and magnetostratigraphic analysis presented in the companion paper by Horton et al. <2004>. Analysis of paleomagnetic declination combined with results from previous studies yield a remarkably consistent trend of vertical axis tectonic rotations across the studied region. Whereas 19.0 ¿ 7.2¿ to 37.8 ¿ 10.6¿ clockwise rotations are recorded consistently in all paleomagnetic localities in Lower Cretaceous to Eocene rocks, all paleomagnetic localities in Oligocene to Pliocene rocks have recorded minor to insignificant rotations, indicating that the Xining-Lanzhou region has undergone a wholesale regional clockwise rotation during late Paleogene time. Consistent with regional chronostratigraphic and thermochronologic results, this late Paleogene tectonic rotation confirms that deformation reached regions of the northern Tibetan Plateau shortly after the initial collision of India with Asia. When compared to rotational paleomagnetic results from adjacent regions, several mechanisms can be proposed to explain the clockwise rotation. On the basis of consistency with geologic data we prefer a model involving clockwise rotation of the Xining-Lanzhou region through right-lateral shear, and associated shortening, related to northward indentation of the Qaidam basin.