The widespread occurrence of Wolbachia in arthropods and nematodes suggests that this intracellular, maternally inherited endosymbiont has the ability to cross species boundaries. However, direct evidence for such a horizontal transmission of Wolbachia in nature is scarce. Here, we compare the well-characterized Wolbachia infection of the European cherry fruit fly, Rhagoletis cerasi, with that of the North American eastern cherry fruit fly, Rhagoletis cingulata, recently introduced to Europe. Molecular genetic analysis of Wolbachia based on multilocus sequence typing and the Wolbachia surface protein wsp showed that all R. cingulata individuals are infected with wCin2 identical to wCer2 in R. cerasi. In contrast, wCin1, a strain identical to wCer1 in R. cerasi, was present in several European populations of R. cingulata, but not in any individual from the United States. Surveys of R. cingulata from Germany and Hungary indicated that the frequency of wCin1 infection increased dramatically in just a few years with at least two independent horizontal transmission events in Germany and Hungary. This is further corroborated by the analysis of the mitochondrial cytochrome oxidase II gene that showed linkage of wCin1 with two distinct haplotypes in Germany, one of which is also infected with wCin1 in Hungary. In summary, our study provides strong evidence for a very recent interspecific Wolbachia transmission with a subsequent spatial spread in field populations.