The ichthyofauna of the Lake Victoria ecosystem are among the most globally threatened biodiversity as a result of anthropogenic and other ecological impacts. Barbus, have vanished from the main lake and sought refuge in the basin's riverine ecosystems, dams, and adjacent satellite lakes. Labeobarbus sp. There is need to identify remaining populations for purposes of conservation and management. In this study, genetic characterization of the endangered cyprinid species in four main rivers (Nzoia, Nyando, Yala and Sondu-Miriu) draining Lake Victoria was carried out. To assess genetic diversity and phylogeny of this species, 619bp of Cytochrome c Oxidase I (CO1) were used. The samples from the four rivers yielded 5 haplotypes. Haplotype 2, in three rivers Nyando, Nzoia and Sondu-Miriu and haplotype 3 was in rivers Nyando, Nzoia and Yala. Samples from Nyando were distributed into four clades. The FST comparisons indicated highest genetic structuring among the Nzoia and Nyando populations (0.6909), whereas Clade-I samples were significantly differentiated from the Sondu-Miriu and Clade-II samples (0.68583). Phylogenetic trees displayed two distinct Clades with clade-I having samples from Nzoia while Clade-II had samples from all the four Kenyan rivers. River Nzoia populations probably represents phylogenetically different populations of L. altianalis. Neighbour joining, maximum parsimony and Bayesian inference analyses yielded congruent trees. Two major clades (A and B) were formed. Clade-A (83/85/0.91) comprised Barbus species forming a sister relationship to Labeobarbus and the experimental sequences. Further the major sub-clade D (90/87/0.99) comprised the subclades E, containing Labeobarbus altianalis from the rivers Nzoia, Yala, Nyando and Sondu-Miriu. Clade-H showed a comparative mixed unsupported clade comprising 5 Labeobarbus species. Within moderate clade-G (67/72/0.81), supported Labeobarbus intermedius which were sister to Clade-J (90/94/0.98) comprising from the Nzoia River. The degree of population differentiation backed with high number of river specific haplotypes, and highly supported bootstrap values of phylogenetic trees is too high to explain the impacts of anthropogenic alone but suggests that the species has probably existed in the Lake Victoria catchment. This existence of genetically robust population of Labeobarbus sp. in the L. Victoria catchment rivers should provide new impetus for conservation of these species.