Monogenea is one of the most species-rich groups of parasitic flatworms worldwide, with many species described only recently, which is particularly true for African monogeneans. For example, Cichlidogyrus, a genus mostly occurring on African cichlids, comprises more than 100 nominal species. Twenty-two of these have been described from Lake Tanganyika, a famous biodiversity hotspot in which many vertebrate and invertebrate taxa, including monogeneans, underwent unique and spectacular radiations. Given their often high degrees of host specificity, parasitic monogeneans were also used as a potential tool to uncover host species relationships. This study presents the first investigation of the monogenean fauna occurring on the gills of endemic `Gnathochromis' species along the Burundese coastline of Lake Tanganyika.We test whether their monogenean fauna reflects the different phylogenetic position and ecological niche of `Gnathochromis' pfefferi and Gnathochromis permaxillaris. Worms collected from specimens of Limnochromis auritus, a cichlid belonging to the same cichlid tribe as G. permaxillaris, were used for comparison. Morphological as well as genetic characterisation was used for parasite identification. In total, all 73 Cichlidogyrus individuals collected from `G.' pfefferi were identified as C. irenae. This is the only representative of Cichlidogyrus previously described from `G.' pfefferi, its type host. Gnathochromis permaxillaris is infected by a species of Cichlidogyrus morphologically very similar to C. gillardinae. The monogenean species collected from L. auritus is considered as new for science, but sample size was insufficient for a formal description. Our results confirm previous suggestions that `G.' pfefferi as a good disperser is infected by a single monogenean species across the entire Lake Tanganyika. Although G. permaxillaris and L. auritus are placed in the same tribe, Cichlidogyrus sp. occurring on G. permaxillaris is morphologically more similar to C. irenae from `G.' pfefferi, than to the Cichlidogyrus species found on L. auritus. Various evolutionary processes, such as host-switching or duplication events, might underlie the pattern observed in this particular parasite-host system. Additional samples for the Cichlidogyrus species occuring on G. permaxillaris and L. auritus are needed to unravel their evolutionary history by means of (co-)phylogenetic analyses.