Cedrelospermum Saporta is an extinct genus in the Ulmaceae with abundant fossil records in North America and Europe. However, so far, fossil records of this genus from Asia are sparse, which limits the interpretations of the morphological evolution and biogeographical history of the genus. Here we report well-preserved fruits (Cedrelospermum tibeticum sp. nov.) and a leaf (Cedrelospermum sp.) of Cedrelospermum from the upper Oligocene Lunpola and Nyima basins in the Qinghai-Tibetan Plateau (QTP). This is the first fossil record of Cedrelospermum in the QTP, showing that this genus grew in this region during the late Oligocene. Cedrelospermum tibeticum fruits are double-winged, morphologically similar to the Eocene and Oligocene double-winged Cedrelospermum species from North America. This supports the hypothesis that Cedrelospermum migrated to Asia from North America by way of the Bering Land Bridge. Given that Cedrelospermum was a typical element of Northern Hemispheric flora in the Paleogene and Neogene, the presence of this genus indicates that the central region of the QTP was phytogeographically linked with other parts of the Northern Hemisphere during the late Oligocene. The morphological observations of C. tibeticum fruits and other double-winged Cedrelospermum fruits suggest an evolutionary trend from obtuse to acute apex for the primary wing. Cedrelospermum tibeticum likely had warm and wet climatic requirements. This type of an environment possibly existed in the central QTP in the late Oligocene, thereby supporting the survival of C. tibeticum.