As one of the largest land mammals, the origin and evolution of the giant rhino Paraceratherium bugtiense in Pakistan have been unclear. We report a new species Paraceratherium linxiaense sp. nov. from northwestern China with an age of 26.5 Ma. Morphology and phylogeny reveal that P. linxiaense is the highly derived species of the genus Paraceratherium, and its clade with P. lepidum has a tight relationship to P. bugtiense. Based on the paleogeographical literature, P. bugtiense represents a range expansion of Paraceratherium from Central Asia via the Tibetan region. By the late Oligocene, P. lepidum and P. linxiaense were found in the north side of the Tibetan Plateau. The Tibetan region likely hosted some areas with low elevation, possibly under 2000 m during Oligocene, and the lineage of giant rhinos could have dispersed freely along the eastern coast of the Tethys Ocean and perhaps through some lowlands of this region.