Host–parasite coevolution has rarely been observed in natural systems. Its study often relies on microparasitic infections introducing a potential bias in the estimation of the evolutionary change of host and parasite traits. Using biological invasions as a tool to study host–parasite coevolution in nature can overcome these biases. We demonstrate this with a cross-infection experiment in the invasive macroparasite Mytilicola intestinalis and its bivalve host, the blue mussel Mytilus edulis. The invasion history of the parasite is well known for the southeastern North Sea and is characterised by two separate invasion fronts that reached opposite ends of the Wadden Sea (i.e. Texel, The Netherlands and Sylt, Germany) in a similar time frame. The species’ natural history thus makes this invasion an ideal natural experiment to study host–parasite coevolution in nature. We infected hosts from Texel, Sylt and Kiel (Baltic Sea, where the parasite is absent) with parasites from Texel and Sylt, to form sympatric, allopatric and naïve infestation combinations, respectively. We measured infection rate, host condition and parasite growth to show that sympatric host–parasite combinations diverged in terms of pre- and post-infection traits within <100 generations since their introduction. Texel parasites were more infective and more efficient at exploiting the host's resources. Hosts on Texel, on the other hand, evolved resistance to infection, whereas hosts on Sylt may have evolved tolerance. This illustrates that different coevolutionary trajectories can evolve along separate invasion fronts of the parasite, highlighting the use of biological invasions in studies of host–parasite coevolution in nature.