The major phylogenetic pattern of the cyprinid tribe Labeonini has been revealed by previous molecular studies; however, the relationships within a clade that mainly inhabits the karst regions, which we refer to as the “karst group”, in southwest China remain unresolved due to the low taxon sampling. This group includes more than 50% of the genera and species of Labeonini in China. Moreover, more than 90% of the genera of this group are endemic to China. In addition, some new genera and species of Labeonini have been discovered from these karst regions, but their taxonomic validity and phylogenetic position have not been examined. In this contribution, partial sequences of four nuclear (exon 3 of recombination activating protein 1, rhodopsin, early growth response protein 2B gene and interphotoreceptor retinoid binding protein gene) and three mitochondrial genes (cytochrome b, cytochrome oxidase subunit I and 16S ribosomal RNA) from 36 ingroup taxa and 25 outgroup taxa were analyzed to provide a hypothesis of the phylogenetic relationships within the labeonins of the karst regions in China. We propose that the monophyly of Parasinilabeo, Ptychidio, Rectoris and Semilabeo are supported. A new genus, Prolixicheilus, is erected for Pseudogyrinocheilus longisulcus. Cophecheilus bamen is the sister to Prolixicheilus longisulcus. Ptychidio, Pseudocrossocheilus, Semilabeo, Rectoris and Stenorynchoacrum are closely related with high support values. Sinocrossocheilus, Pseudogyrinocheilus, Paraqianlabeo, Hongshuia, Discogobio and Discocheilus form a clade together with high support. Considering molecular results and morphological differences, Parasinilabeo longicorpus and Ptychidio macrops might be the synonyms of Parasinilabeo assimilis and Ptychidio jordani respectively. Comprehensive taxonomic revisions of the two genera Parasinilabeo and Ptychidio may be necessary.