Wolbachia is a maternally-transmitted endosymbiotic bacteria that infects a large diversity of arthropod and nematode hosts. Some strains of Wolbachia are parasitic, manipulating host reproduction to benefit themselves, while other strains of Wolbachia exhibit obligate or facultative mutualisms with their host. The effects of Wolbachia on its host are many, though primarily relate to host immune and reproductive function. Here we test the hypothesis that Wolbachia infection alters the frequency of homologous recombination during meiosis. We use D. melanogaster as a model system, and survey recombination in eight wild-derived Wolbachia-infected (strain wMel) and Wolbachia-uninfected strains, controlling for genotype. We measure recombination in two intervals of the genome. Our results indicate that Wolbachia infection is associated with increased recombination in one genomic interval and not the other. The effect of Wolbachia infection on recombination is thus heterogenous across the genome. Our data also indicate a reproductive benefit of Wolbachia infection; infected females show higher fecundity than their uninfected genotypic controls. Given the prevalence of Wolbachia infection in natural populations, our findings suggest that Wolbachia infection is likely to contribute to recombination rate and fecundity variation among individuals in nature.