The symbiotic relationship between Asaia, an α-proteobacterium belonging to the family Acetobacteriaceae, and mosquitoes has been studied mainly in the Asian malaria vector Anopheles stephensi. Thus, we have investigated the nature of the association between Asaia and the major Afro-tropical malaria vector Anopheles gambiae. We have isolated Asaia from different wild and laboratory reared colonies of A. gambiae, and it was detected by PCR in all the developmental stages of the mosquito and in all the specimens analyzed. Additionally, we have shown that it localizes in the midgut, salivary glands and reproductive organs. Using recombinant strains of Asaia expressing fluorescent proteins, we have demonstrated the ability of the bacterium to colonize A. gambiae mosquitoes with a pattern similar to that described for A. stephensi. Finally, fluorescent in situ hybridization on the reproductive tract of females of A. gambiae showed a concentration of Asaia at the very periphery of the eggs, suggesting that transmission of Asaia from mother to offspring is likely mediated by a mechanism of egg-smearing. We suggest that Asaia has potential for use in the paratransgenic control of malaria transmitted by A. gambiae.