The Haplochromini are by far the most species-rich cichlid fish tribe that originated along with the so-called primary radiation of the Lake Tanganyika cichlid species flock, i.e. at the same time during which the majority of the endemic Lake Tanganyika cichlid tribes emerged. Unlike the other tribes, the haplochromines are not restricted to Lake Tanganyika but distributed throughout Africa, except for the northwestern part of the continent. Haplochromine cichlids seeded the adaptive radiation of cichlid fishes in Lakes Malawi, Kivu, Victoria, Turkana, as well as in the now extinct paleo-Lake Makgadikgadi. Here we present a comprehensive phylogenetic and phylogeographic analysis of haplochromine cichlids that is based upon DNA sequences of two mitochondrial gene segments of riverine taxa covering all major African biogeographic regions where haplochromines are found. Our analysis revealed that six lineages of haplochromines originated within a short period of time, about 5.3-4.4 MYA. These haplochromine lineages show a highly complex phylogeographic pattern, probably severely influenced by climate- and/or geology-induced changes of the environment, with river capture events most likely playing an important role for species dispersal.