Heritable microbes that exhibit reproductive parasitism are common in insects. One class of these are the male-killing bacteria, which are found in a broad range of insect hosts. Commonly, our knowledge of the incidence of these microbes is based on one or a few sampling sites, and the degree and causes of spatial variation are unclear. In this paper, we examine the incidence of the son-killer microbe Arsenophonus nasoniae across European populations of its wasp host, Nasonia vitripennis. In preliminary work, we noticed two female N. vitripennis producing highly female biased sex ratios in a field study from the Netherlands and Germany. When tested, the brood from Germany was revealed to be infected with A. nasoniae. We then completed a broad survey in 2012, in which fly pupal hosts of N. vitripennis were collected from vacated birds’ nests from four European populations, N. vitripennis wasps allowed to emerge and then tested for A. nasoniae presence through PCR assay. We then developed a new screening methodology based on direct PCR assays of fly pupae and applied this to ethanol-preserved material collected from great tit (Parus major) nests in Portugal. These data show A. nasoniae is found widely in European N. vitripennis, being present in Germany, the UK, Finland, Switzerland and Portugal. Samples varied in the frequency with which they carry A. nasoniae, from being rare to being present in 50% of the pupae parasitised by N. vitripennis. Direct screening of ethanol-preserved fly pupae was an effective method for revealing both wasp and A. nasoniae infection, and will facilitate sample transport across national boundaries. Future research should examine the causes of variation in frequency, in particular testing the hypothesis that N. vitripennis superparasitism rates drive the variation in A. nasoniae frequency through providing opportunities for infectious transmission.