The maternally inherited alpha-proteobacterium Wolbachia has been proposed as a tool to block transmission of devastating mosquito-borne infectious diseases like dengue and malaria. Here we study the reproductive manipulations induced by a recently identified Wolbachia strain that stably infects natural mosquito populations of a major malaria vector, Anopheles coluzzii, in Burkina Faso. We determine that these infections significantly accelerate egg laying but do not induce cytoplasmic incompatibility or sex-ratio distortion, two parasitic reproductive phenotypes that facilitate the spread of other Wolbachia strains within insect hosts. Analysis of 221 blood-fed A. coluzzii females collected from houses shows a negative correlation between the presence of Plasmodium parasites and Wolbachia infection. A mathematical model incorporating these results predicts that infection with these endosymbionts may reduce malaria prevalence in human populations. These data suggest that Wolbachia may be an important player in malaria transmission dynamics in Sub-Saharan Africa.