Symbiotic bacteria have been proposed as tools for control of insect-borne diseases. Primary requirements for such symbionts are dominance, prevalence and stability within the insect body. Most of the bacterial symbionts described to date in Anopheles mosquitoes, the vector of malaria in humans, have lacked these features. We describe an a-Proteobacterium of the genus Asaia, which stably associates with several Anopheles species and dominates within the body of An. Stephensi. Asaia exhibits all the required ecological characteristics making it the best candidate, available to date, for the development of a paratransgenic approach for manipulation of mosquito vector competence. Key features of Asaia are: (i) dominance within the mosquito-associated microflora, as shown by clone prevalence in 16S rRNA gene libraries and quantitative real time Polymerase Chain Reaction (qRT-PCR); (ii) cultivability in cell-free media; (iii) ease of transformation with foreign DNA and iv) wide distribution in the larvae and adult mosquito body, as revealed by transmission electron microscopy, and in situ-hybridization experiments. Using a green fluorescent protein (GFP)-tagged Asaia strain, it has been possible to show that it effectively colonizes all mosquito body organs necessary for malaria parasite development and transmission, including female gut and salivary glands. Asaia was also found to massively colonize the larval gut and the male reproductive system of adult mosquitoes. Moreover, mating experiments showed an additional key feature necessary for symbiotic control, the high transmission potential of the symbiont to progeny by multiple mechanisms. Asaia is capable of horizontal infection through an oral route during feeding both in preadult and adult stages and through a venereal pattern during mating in adults. Furthermore, Asaia is vertically transmitted from mother to progeny indicating that it could quickly spread in natural mosquito populations.