Migratory detritivores of the characiform family Prochilodontidae occur throughout the freshwaters of much of South America. Prochilodontids often form massive populations and many species achieve substantial body sizes; a combination that makes them one of the most commercially important fish groups on the continent. Their economic significance notwithstanding, prochilodontids have never been the subject of a comprehensive molecular phylogenetic analysis. Using three mitochondrial and three nuclear loci spanning all prochilodontid species, we generated a novel phylogenetic hypothesis for the family. Our results strongly support monophyly of the family and the three included genera. A novel, highly supported placement of Ichthyoelephas sister to the clade containing Prochilodus and Semaprochilodus diverges from a previous morphological hypothesis. Most previously hypothesized interspecific relationships are corroborated and some longstanding polytomies within Prochilodus and Semaprochilodus are resolved. The morphologically similar P. brevis, P. lacustris, P. nigricans and P. rubrotaeniatus are embedded within what is herein designated as the P. nigricans group. Species limits and distributions of these species are problematic and the group clearly merits taxonomic revision.