Aphids are a serious threat to agriculture, despite being a rather small group of insects. The about 4,000 species worldwide engage in highly interesting and complex relationships with their microbial fauna. One of the key symbionts in arthropods is Wolbachia, an α-Proteobacterium implicated in many important biological processes and believed to be a potential tool for biological control. Aphids were thought not to harbour Wolbachia; however, current data suggest that its presence in aphids has been missed, probably due to the low titre of the infection and/or to the high divergence of the Wolbachia strains of aphids. The goal of the present study is to map the Wolbachia infection status of natural aphids populations, along with the characterization of the detected Wolbachia strains. Out of 425 samples from Spain, Portugal, Greece, Israel and Iran, 37 were found to be infected. Our results, based mainly on 16S rRNA gene sequencing, indicate the presence of two new Wolbachia supergroups prevailing in aphids, along with some strains belonging either to supergroup B or to supergroup A.