During the last decade, the endosymbiont bacterium Wolbachia has emerged as a biological tool for vector disease control. However, for long time, it was believed that Wolbachia was absent in natural populations of Anopheles. The recent discovery that species within the Anopheles gambiae complex host Wolbachia in natural conditions has opened new opportunities for malaria control research in Africa. Here, we investigated the prevalence and diversity of Wolbachia infection in 25 African Anopheles species in Gabon (Central Africa). Our results revealed the presence of Wolbachia in 16 of these species, including the major malaria vectors in this area. The infection prevalence varied greatly among species, confirming that sample size is a key factor to detect the infection. Moreover, our sequencing and phylogenetic analyses showed the important diversity of Wolbachia strains that infect Anopheles. Co-evolutionary analysis unveiled patterns of Wolbachia transmission within some Anopheles species, suggesting that past independent acquisition events were followed by co-cladogenesis. The large diversity of Wolbachia strains that infect natural populations of Anopheles offers a promising opportunity to select suitable phenotypes for suppressing Plasmodium transmission and/or manipulating Anopheles reproduction, which in turn could be used to reduce the malaria burden in Africa.