The Lake Edward system in Eastern Central Africa, including Lakes Edward and George and their associated rivers, is home to a species assemblage of endemic haplochromine cichlids. Currently, 36 of these species have been formally described, while it is estimated that the system may harbour a total of 60 species. Species flocks of haplochromine cichlids are morphologically and ecologically very diverse and have radiated into many specialised trophic niches. Paedophagy is the feeding on eggs and larvae. In Haplochromis, most paedophages steal fry and eggs from the buccal cavities of mouthbrooding female cichlids. Hitherto, one formally described species with this diet is known from the Lake Edward system: Haplochromis taurinus. We performed a morphometrical revision of all species of Haplochromis from this system with a morphology that suggests a paedophagous diet: long oral jaws set with small teeth. Sixty-eight specimens were studied by taking 28 measurements and 20 counts and by performing stomach content observations. We discovered that H. paradoxus also had a paedophagous diet. Our analyses further revealed the presence of three new species: H. gracilifur sp. nov., H. molossus sp. nov., and H. relictidens sp. nov. All five of these species were described or redescribed.