Hosts and parasites have often intimate associations. Therefore, the evolution of their interactions is crucial for understanding species-rich host-parasite communities. Yet relatively few studies investigate eco-evolutionary feedbacks in these systems as large datasets remain scarce. Here, we explore African cichlid fishes and their flatworm gill parasites (Cichlidogyrus spp.) including 9901 reported infections and 473 different host-parasite combinations collected through a survey of peer-reviewed literature. We apply network metrics, estimate host repertoires, and use network link prediction (NLP) algorithms to investigate meta-community structures and their predictors including evolutionary, ecological, and morphological parameters. Host repertoire was mostly determined by the hosts’ evolutionary history. Both ecological and evolutionary parameters predicted host parasite associations but many interactions remain undetected according to NLP. We conclude that ecological opportunity paired with ecological fitting has shaped interactions. The cichlid-Cichlidogyrus network is a suitable study system for eco-evolutionary feedbacks but taxonomic research remains key to finding undetected interactions.