African cichlids are model systems for evolutionary studies and host-parasite interactions, because of their adaptive radiations and because they harbour many species of monogenean parasites with high host-specificity. Five locations were sampled in southern Lake Victoria: gill-infecting monogeneans were surveyed from 18 cichlid species belonging to this radiation superflock and two others representing two older and distantly related lineages. We found one species of Gyrodactylidae, Gyrodactylus sturmbaueri Vanhove, Snoeks, Volckaert & Huyse, 2011, and seven species of Dactylogyridae. Four are described herein: Cichlidogyrus pseudodossoui n. sp., Cichlidogyrus nyanza n. sp., Cichlidogyrus furu n. sp., and Cichlidogyrus vetusmolendarius n. sp. Another Cichlidogyrus species is reported but not formally described (low number of specimens, morphological similarity with C. furu n. sp.). Two other species are redescribed: C. bifurcatus Paperna, 1960 and C. longipenis Paperna & Thurston, 1969. Our results confirm that the monogenean fauna of Victorian littoral cichlids displays lower species richness and lower host-specificity than that of Lake Tanganyika littoral cichlids. In C. furu n. sp., hooks V are clearly longer than the others, highlighting the need to re-evaluate the current classification system that considers hook pairs III–VII as rather uniform. Some morphological features of C. bifurcatus, C. longipenis, and C. nyanza n. sp. suggest that these are closely related to congeners that infect other haplochromines. Morphological traits indicate that representatives of Cichlidogyrus colonised Lake Victoria haplochromines or their ancestors at least twice, which is in line with the Lake Victoria superflock being colonised by two cichlid tribes (Haplochromini and Oreochromini).