The cyprinid tribe Labeonini (sensu Rainboth, 1991) is a large group of freshwater fishes containing around 40 genera and 400 species. They are characterized by an amazing diversity of modifications to their lips and associated structures. In this study, a total of 34 genera and 142 species of putative members of this tribe, which represent most of the generic diversity and more than one third of the species diversity of the group, were sampled and sequenced for four nuclear genes and five mitochondrial genes (totalling 9,465 bp). Phylogenetic relationships and subdivision of this tribe were investigated and the placement and status of most genera are discussed. Partitioned maximum likelihood analyses were performed based on the nuclear dataset, mitochondrial dataset, combined dataset, and the dataset for each nuclear gene. Inclusion of the genera Paracrossochilus, Barbichthys, Thynnichthys, and Linichthys in the Labeonini was either confirmed or proposed for the first time. None of the genera Labeo, Garra, Bangana, Cirrhinus, and Crossocheilus are monophyletic. Taxonomic revisions of some genera were made: the generic names Gymnostomus Heckel, 1843, Ageneiogarra Garman, 1912 and Gonorhynchus McClelland, 1839 were revalidated; Akrokolioplax Zhang and Kottelat, 2006 becomes a junior synonym of Gonorhynchus; the species Osteochilus nashii was found to be a member of the barbin genus Osteochilichthys. Five historical hypotheses on the classification of the Labeonini were tested and rejected. We proposed to subdivide the tribe, which is strongly supported as monophyletic, into four subtribes: Labeoina, Garraina, Osteochilina, and Semilabeoina. The taxa included in each subtribe were listed and those taxa that need taxonomic revision were discussed.