Invasive species can displace natives, and thus identifying the traits that make aliens successful is crucial for predicting and preventing biodiversity loss. Pathogens may play an important role in the invasive process, facilitating colonization of their hosts in new continents and islands. According to the Novel Weapon Hypothesis, colonizers may out-compete local native species by bringing with them novel pathogens to which native species are not adapted. In contrast, the Enemy Release Hypothesis suggests that flourishing colonizers are successful because they have left their pathogens behind. To assess the role of avian malaria and related haemosporidian parasites in the global spread of a common invasive bird, we examined the prevalence and genetic diversity of haemosporidian parasites (order Haemosporida, genera Plasmodium and Haemoproteus) infecting house sparrows (Passer domesticus). We sampled house sparrows (N = 1820) from 58 locations on 6 continents. All the samples were tested using PCR-based methods; blood films from the PCR-positive birds were examined microscopically to identify parasite species. The results show that haemosporidian parasites in the house sparrows' native range are replaced by species from local host-generalist parasite fauna in the alien environments of North and South America. Furthermore, sparrows in colonized regions displayed a lower diversity and prevalence of parasite infections. Because the house sparrow lost its native parasites when colonizing the American continents, the release from these natural enemies may have facilitated its invasion in the last two centuries. Our findings therefore reject the Novel Weapon Hypothesis and are concordant with the Enemy Release Hypothesis.