The faunal diversity of Lake Tanganyika, with its fish species flocks and its importance as a cradle and reservoir of ancient fish lineages seeding other radiations, has generated a considerable scientific interest in the fields of evolution and biodiversity. The Tropheini, an endemic Tanganyikan cichlid tribe, fills a peculiar phylogenetic position, being closely related to the haplochromine radiations of Lakes Malawi and Victoria. Several problems remain regarding their genus-level classification. For example, the monotypic genus Interochromis is phylogenetically nested within Petrochromis; its only representative, I. loocki, has often been reclassified. As monogenean flatworms are useful markers for fish phylogeny and taxonomy, the monogenean fauna of Interochromis loocki was examined and compared to that of other tropheine cichlids. Three new monogenean species belonging to Cichlidogyrus are described from Interochromis loocki: Cichlidogyrus buescheri Pariselle and Vanhove, sp. nov., Cichlidogyrus schreyenbrichardorum Pariselle and Vanhove, sp. nov. and Cichlidogyrus vealli Pariselle and Vanhove, sp. nov. Their haptoral anchors remind more of congeners infecting species of Petrochromis than of all Cichlidogyrus spp. hitherto described from other tropheine cichlids. Attachment organ morphology has been proven to mirror the phylogenetic affinities of Cichlidogyrus lineages. Therefore the monogenean parasite fauna of I. loocki reflects this host’s position within Petrochromis. Moreover, I. loocki differs in habitat choice from Petrochromis spp. This study hence confirms that host range and host-specificity in Cichlidogyrus spp. parasitizing tropheines is determined by the host’s phylogenetic position, rather than by a shared ecological niche.