Lake Tanganyika, the oldest lake in Africa, harbors the most genetically, morphologically and ecologically diverse cichlid assemblages of the African Great Lakes. Its mostly endemic cichlids are considered as a model to study adaptive radiation and rapid diversification. Because of the apparently high host specificity of gill monogeneans, phylogenetic studies using molecular data of these parasites offer an interesting additional approach to study their host’s diversity, evolution and host-parasite interactions. Cichlids in Africa are known to host five different genera of dactylogyridean, Cichlidogyrus being the most diverse with more than 95 species recorded from more than 70 cichlids. Members of Cichlidogyrus are gill ectoparasites. To recognize different species of Cichlidogyrus, morphological data (haptor and male copulatory organs (MCO)) in addition to molecular sequence analyses are used. The goal of this study is to investigate the phylogenetic affinities between the Cichlidogyrus fauna of different Tanganyika cichlid tribes using different molecular markers (28S rDNA, 18S rDNA, ITS-1 and COX1). Then, for first time in Lake Tanganyika and from Cyprichromis microlepidotus, monogenean species is described. In addition, we zoom on the host-parasite relationship of species of Cichlidogyrus infecting two cichlid tribes: Haplochromini and Eretmodini. An evaluation of the phylogenetic relationships of cichlid mononeneans parasitizing the different Lake Tanganyika cichlid tribes may help us to elucidate the historic and ecological relationships between cichlid tribes and to determine the origin of Cichlidogyrus of Lake Tanganyika cichlids.