The Eurasian barbs, the genus Barbus, are distributed mainly in drainages of Mediterranean, Black and Caspian Sea basins. The barbels are one of the common fish in the rivers of the Caucasus Mountains situated between Black and Caspian Seas. Despite most of Caucasian Barbus species were already studied phylogenetically by mtDNA marker cytb, the samples used in these studies were represented by one-two specimens. We sampled Caucasian rivers more intensively and checked all main drainages as well as several isolated rivers of Eastern Black Sea drainage (n = 104). Phylogenetic analysis based on two markers of mtDNA (COI and cytb) has confirmed four lineages previously reported in Caucasian rivers: B. ciscaucasicus, B. cyri, B. escherichii, and B. kubanicus as well as revealed a new lineage, locally distributed in rivers of Eastern part of Black Sea drainage. Probably new lineage is associated with B. rionicus that was synonymized previously with B. escherichii. The Sevan barbel B. goktschaicus is identical to B. cyri, and we consider the former as conspecific with the latter. Due to extended geographic coverage, we also clarified current ranges of species based on both genetic and morphologic analyses.