Interspecific symbiotic relationships involve a complex network of interactions, and understanding their outcome requires quantification of the costs and benefits to both partners. We experimentally investigated the costs and benefits in the relationship between European bitterling fish (Rhodeus sericeus) and freshwater mussels that are used by R. sericeus for oviposition. This relationship has hitherto been thought mutualistic, on the premise that R. sericeus use mussels as foster parents of their embryos while mussels use R. sericeus as hosts for their larvae. We demonstrate that R. sericeus is a parasite of European mussels, because it (i) avoids the cost of infection by mussel larvae and (ii) imposes a direct cost on mussels. Our experiments also indicate a potential coevolutionary arms race between bitterling fishes and their mussel hosts; the outcome of this relationship may differ between Asia, the centre of distribution of bitterling fishes, and Europe where they have recently invaded.