The Qaidam Basin, lying in the north-eastern Tibetan Plateau, China, is key to understanding the Cenozoic climatic and biological changes that have occurred on the plateau; however, information from a palaeontological perspective on this Palaeogene basin is scant. Recently, fossil cyprinids were found in the middle portion of the Shangganchaigou Formation (= Upper Ganchaigou Formation; Oligocene) in the north-western Qaidam Basin. These share many osteological characters with barbines and 'morphologically primitive clade schizothoracines' (= primitive schizothoracines; i.e. Schizothorax and Aspiorhynchus), and they closely resemble the latter in the size and shape of the scales: body scales are small and oval; the number of lateral line scales exceeds 100; and the long-oval scales from the pre-anal region are very similar to the 'anal scales', which are unique to schizothoracines. Compared with another fossil fish, Paleoschizothorax qaidamensis, from the same formation, the major differences are: (1) the posterior part of the entopterygoid in the new material is normal and not expanded while that of P. qaidamensis is obviously expanded; and (2) the premaxilla process of maxilla is well developed in P. qaidamensis but weak in the new specimens. Therefore, they are described as a new species of the fossil genus Paleoschizothorax (subfamily Schizothoracinae): Paleoschizothorax diluculum sp. nov. A phylogenetic analysis, which included 13 extant genera and three fossil forms of barbines and schizothoracines and 70 morphological characters, also supports the close relationship between P. diluculum and primitive schizothoracines. A preliminary correlation analysis suggests that the degree of reduction of body scale size is negatively correlated with habitat mean temperatures among most Chinese cyprinids. Moreover, we speculate that the 'primitive schizothoracines' likely originated in the north-eastern-central Tibetan Plateau based on the fossil records and molecular phylogeny of the extant taxa.