The impact of multiple invading species can be magnified due to mutual facilitation, termed “invasional meltdown”, but invasive species can also be adversely affected by their interactions with other invaders. Using a unique reciprocal host-parasite relationship between a bitterling fish, Rhodeus amarus, and unionid mussels, we show that an invasive mussel reverses the roles in the relationship. Bitterling lay their eggs into mussel gills, and mussel larvae parasitize fish. Bitterling recently colonized Europe and parasitize all sympatric European mussels, but are unable to utilize a recently invasive mussel, Anodonta woodiana. The parasitic larvae of A. woodiana successfully develop on R. amarus, while larvae of European mussels are rejected by bitterling. This demonstrates that invading species may temporarily benefit from a coevolutionary lag by exploiting evolutionarily naïve hosts, but the resulting relaxed selection may facilitate its exploitation by subsequent invading species, leading to unexpected consequences for established interspecific relationships.