Host-parasite relationships are often characterized by the rapid evolution of parasite adaptations to exploit their host, and counteradaptations in the host to avoid the costs imposed by parasitism. Hence, the current coevolutionary state between a parasite and its hosts is predicted to vary according to the history of sympatry and local abundance of interacting species. We compared a unique reciprocal coevolutionary relationship of a fish, the European bitterling (Rhodeus amarus) and freshwater mussels (Unionidae) between areas of recent (Central Europe) and ancient (Turkey) sympatry. Bitterling parasitize freshwater mussels by laying their eggs in the gills of mussel and, in turn, mussel larvae (glochidia) parasitize the fish. We found that all bitterling from both regions avoided one mussel species. Preferences among other mussel species tended to be related to local mussel abundance rather than duration of sympatry. Individual fish were not consistent in their oviposition choices, precluding the evolution of host-specific lineages. Mussels were demonstrated to have evolved strong defenses to bitterling parasitism in the area of ancient sympatry, but have no such defenses in the large areas of Europe where bitterling are currently invasive. Bitterling avoided glochidia infection irrespective of the duration of sympatry.