The success of introduced species is frequently explained by their escape from natural enemies in the introduced region. We tested the enemy release hypothesis with respect to two well studied blood parasite genera (Plasmodium and Haemoproteus) in native and six introduced populations of the common myna Acridotheres tristis. Not all comparisons of introduced populations to the native population were consistent with expectations of the enemy release hypothesis. Native populations show greater overall parasite prevalence than introduced populations, but the lower prevalence in introduced populations is driven by low prevalence in two populations on oceanic islands (Fiji and Hawaii). When these are excluded, prevalence does not differ significantly. We found a similar number of parasite lineages in native populations compared to all introduced populations. Although there is some evidence that common mynas may have carried parasite lineages from native to introduced locations, and also that introduced populations may have become infected with novel parasite lineages, it may be difficult to differentiate between parasites that are native and introduced, because malarial parasite lineages often do not show regional or host specificity.