Here, we show that an alpha-proteobacterium of the genus Asaia is stably associated with larvae and adults of Anopheles stephensi, an important mosquito vector of Plasmodium vivax, a main malaria agent in Asia. Asaia bacteria dominate mosquito-associated microbiota, as shown by 16S rRNA gene abundance, quantitative PCR, transmission electron microscopy and in situ-hybridization of 16S rRNA genes. In adult mosquitoes, Asaia sp. is present in high population density in the female gut and in the male reproductive tract. Asaia sp. from An. stephensi has been cultured in cell-free media and then transformed with foreign DNA. A green fluorescent protein-tagged Asaia sp. strain effectively lodged in the female gut and salivary glands, sites that are crucial for Plasmodium sp. development and transmission. The larval gut and the male reproductive system were also colonized by the transformed Asaia sp. strain. As an efficient inducible colonizer of mosquitoes that transmit Plasmodium sp., Asaia sp. may be a candidate for malaria control.