Interspecific brood parasitism occurs in several independent lineages of birds and social insects, putatively evolving from intraspecific brood parasitism. The cuckoo catfish, Synodontis multipunctatus , the only known obligatory non-avian brood parasite, exploits mouthbrooding cichlid fishes in Lake Tanganyika, despite the absence of parental care in its evolutionary lineage (family Mochokidae). Cuckoo catfish participate in host spawning events, with their eggs subsequently collected and brooded by parental cichlids, though they can later be selectively rejected by the host. One scenario for the origin of brood parasitism in cuckoo catfish is through predation of cichlid eggs during spawning, eventually resulting in a spatial and temporal match in oviposition by host and parasite. Here we demonstrate experimentally that, uniquely among all known brood parasites, cuckoo catfish have the capacity to re-infect their hosts at a late developmental stage following egg rejection. We show that cuckoo catfish offspring can survive outside the host buccal cavity and re-infect parental hosts at a later incubation phase by exploiting the strong parental instinct of hosts to collect stray offspring. This finding implies an alternative evolutionary origin for cuckoo catfish brood parasitism, with the parental response of host cichlids facilitating its evolution. This article is part of the theme issue ‘The coevolutionary biology of brood parasitism: from mechanism to pattern’.