Introduced species have the potential to outperform natives via the introduction of new parasites to which the native ecosystem is vulnerable. Cryptic diversity within an invasive species can obscure invasion patterns and confound proper management measures. The aim of this study is to use coalescent theory based methodology to trace recent routes of invasion in populations of Ligula intestinalis, a globally distributed fish parasite possessing both native and recently introduced populations in North Africa. Molecular analyses of mitochondrial DNA discerned a pronounced genetic divergence between introduced and native populations. Distribution of mitochondrial haplotypes demonstrated common origin of European populations with North African parasites sampled from introduced fish species in Tunisia. To test the suggested pathway of introduction, microsatellite data were examined in a model-based coalescent analysis using the software MIGRATE, where Europe to Tunisia direction of migration was favoured over alternative hypotheses of gene flow. Specificity of Tunisian populations to different host species was assessed in an epidemiologic survey confirming prevailing host-based division between introduced and native parasites in North Africa. This approach combining advanced analysis of molecular markers with host-specificity data allows revealing the evolution of host-parasite interactions following biological invasion and provides basis for devising future management measurements.