Monophyly of the genus Leporinus (Characiformes: Anostomidae) was tested by sequencing and analysing a total of 4732 bp, including two mitochondrial [cytochrome oxidase subunit 1 (CO1) and cytochrome b (Cytb)] and three nuclear [myosin heavy chain 6 cardiac muscle alpha (Myh6), recombination activating gene 1 (RAG1) and recombination activating gene 2 (RAG2)] loci for 22 species of Leporinus, or c. 25% of all described species in the genus. Phylogenetic tree analyses (maximum parsimony, maximum likelihood and Bayesian species tree) indicate Leporinus to be paraphyletic, with monophyly being rejected by both Kishino-Hasegawa and Shimodaira-Hasegawa tests. The sequenced species of Leporinus are distributed across five clades that are interleaved among other anostomid genera. Several taxonomic changes are suggested as being necessary to restore monophyly for the group. The clade containing the type species, Leporinus fasciatus, should be considered Leporinus sensu stricto and at least three new genera should be described for other species currently considered part of Leporinus.