ABSTRACT Obligate brood parasites delegate the workload of costly parental care to their hosts. Theory predicts that release from demanding parental care increases the importance of other factors to shape mating patterns. However, behavioural observations and parentage estimates are notoriously difficult to obtain in species with covert reproductive strategies, such as brood parasites, and evidence for their mating strategies are scarce. Molecular genetic methods provide a powerful tool to identify concealed mating patterns. Here, we reconstruct the parentage of cuckoo catfish ( Synodontis multipunctatus ) clutches collected in the wild using a combination of newly developed microsatellite markers, mitochondrial markers, and maximum likelihood estimates of pairwise relatedness. Cuckoo catfish parasitise mouthbrooding cichlids in Lake Tanganyika, but a natural spawning of the brood parasite has never been observed. We examined 429 females of confirmed host cichlid species (parasitism prevalence 6%; 24 parasitised clutches with 1–14 embryos) and found that 46% of clutches with three or more offspring (i.e., 6 out of 13) were parented by more than two catfish individuals. We demonstrated variable mating patterns including polyandrous and polygynous mating, and host sharing by separate, genetically monogamous, catfish pairs. This indicates that cuckoo catfish parasitism involves groups of catfish with reduced capability to monopolise mating opportunities. In general, our results demonstrate how reproductive strategy and mating patterns in a species with concealed breeding behaviour can be investigated and provide valuable insights into the mating system of a brood parasitic species other than hitherto studied avian brood parasites.