Coevolutionary relationships between parasites and hosts can elevate the rate of evolutionary changes due to reciprocal adaptations between coevolving partners. Such relationships can result in the evolution of host specificity. Recent methodological advances have permitted the recognition of cryptic lineages, with important consequences for our understanding of biological diversity. We used the European bitterling (Rhodeus amarus), a freshwater fish that parasitizes unionid mussels, to investigate host specialization across regions of recent and ancient sympatry between coevolving partners. We combined genetic data (12 microsatellite and 2 mitochondrial markers) from five populations with experimental data for possible mechanisms of host species recognition (imprinting and conditioning). We found no strong evidence for the existence of cryptic lineages in R. amarus, though a small proportion of variation among individuals in an area of recent bitterling-mussel association was statistically significant in explaining host specificity. No other measures supported the existence of host-specific lineages. Behavioural data revealed a weak effect of conditioning that biased behavioural preferences toward specific host species. Host imprinting had no effect on oviposition behaviour. Overall, we established that populations of R. amarus show limited potential for specialization, manifested as weak effects of host conditioning and genetic within-population structure. Rhodeus amarus is the only species of mussel-parasitizing fish in Europe, which contrasts with the species-rich communities of bitterling in eastern Asia where several host-specific bitterling occur. We discuss costs and constraints on the evolution of host-specific lineages in our study system and more generally.