Complete mitochondrial cytochrome b sequences of 54 species, including 18 newly sequenced, were analyzed to infer the phylogenetic relationships within the family Cyprinidae in East Asia. Phylogenetic trees were generated using various tree-building methods, including Neighbor-joining (NJ), Maximum Parsimony (MP) and Maximum Likelihood (ML) methods, with Myxocyprinus asiaticus (family Catostomidae) as the designated outgroup. The results from NJ and ML methods were mostly similar, supporting some existing subfamilies within Cyprinidae as monophyletic, such as Cultrinae, Xenocyprinae and Gobioninae (including Gobiobotinae). However, genera within the subfamily "Danioninae" did not form a monophyletic group. The subfamily Leuciscinae was divided into two unrelated groups: the "Leuciscinae" in East Asia forming as a monophyletic group together with Cultrinae and Xenocyprinae, while the Leucisciriae in Europe, Siberia, and North America as another monophyletic group. The monophyly of subfamily Cyprininae sensu Howes was supported by NJ and ML trees and is basal in the tree. The position of Acheilognathinae, a widely accepted monophyletic group represented by Rhodeus sericeus, was not resolved.