Symbiotic bacteria are known to play important roles in the biology of insects, but the current knowledge of bacterial communities associated with mosquitoes is very limited and consequently their contribution to host behaviors is mostly unknown. In this study, we explored the composition and diversity of mosquito-associated bacteria in relation with mosquitoes' habitats. Wild Aedes albopictus and Aedes aegypti were collected in three different geographic regions of Madagascar. Culturing methods and denaturing gradient gel electrophoresis (DGGE) and sequencing of the rrs amplicons revealed that Proteobacteria and Firmicutes were the major phyla. Isolated bacterial genera were dominated by Bacillus, followed by Acinetobacter, Agrobacterium and Enterobacter. Common DGGE bands belonged to Acinetobacter, Asaia, Delftia, Pseudomonas, Enterobacteriaceae and an uncultured Gammaproteobacterium. Double infection by maternally inherited Wolbachia pipientis prevailed in 98% of males (n=272) and 99% of females (n=413); few individuals were found to be monoinfected with Wolbachia wAlbB strain. Bacterial diversity (Shannon-Weaver and Simpson indices) differed significantly per habitat whereas evenness (Pielou index) was similar. Overall, the bacterial composition and diversity were influenced both by the sex of individuals and by the environment inhabited by the mosquitoes; the latter might be related to both the vegetation and the animal host populations that Aedes used as food sources.