The phylogenetic relationships of 106 European cyprinid taxa were determined based on the complete nucleotide sequence (1140 bp) of the mitochondrial cytochrome b gene. The molecular phylogeny was used (1) to revise the current systematics of European cyprinids, (2) to establish the phylogenetic utility of traditional morphological characters that are widely used in Cyprinidae systematics, and (3) to discuss alternative hypotheses on the biogeography of the family in Europe. The age of the major lineages within European cyprinids was tentatively estimated with a molecular clock and showed full agreement with the fossil record of the group. Moreover, the results provided unambiguous evidence for a close phylogenetic affinity of some Caucasian and Greek endemic cyprinid taxa (e.g., B. capito and B. brachycephalus and Leuciscus keadicus, Barbus graecus, and B. albanicus, respectively) to Iberian and North African, but not Central European, cyprinids. The existence of such unexpected phylogenetic relationships refutes the classical hypothesis on the biogeography of European cyprinids, which assumes a dispersal of the cyprinid fauna from central Europe to southern Europe and northern Africa during the Miocene (and, hence, predicts a close phylogenetic relationship of all Caucasian, Greek, Iberian, and North African cyprinids to central European taxa). Instead, the existence of a Mediterranean realm independent of the central European route seems plausible based on the molecular evidence. It is likely that the new biogeographical scenario proposed here might apply to other primary freshwater European animals with low dispersal abilities, including fish, amphibians, and invertebrates.