There is increasing evidence of the far-reaching effects of gut bacteria on physiological and behavioural traits, yet the fitness-related consequences of changes in the gut bacteria composition of sexually interacting individuals remain unknown. To address this question, we manipulated the gut microbiota of fruit flies, Drosophila melanogaster, by monoinfecting flies with either Acetobacter pomorum (AP) or Lactobacillus plantarum (LP). Re-inoculated individuals were paired in all treatment combinations. LP-infected males had longer mating duration and induced higher short-term offspring production in females compared with AP-infected males. Furthermore, females of either re-inoculation state mated with AP-infected males were more likely to have zero offspring after mating, suggesting a negative effect of AP on male fertility. Finally, we found that the effects of male and female gut bacteria interacted to modulate their daughters', but not sons' body mass, revealing a new trans-generational effect of parental gut microbiota. In conclusion, this study shows direct and trans-generational effects of the gut microbiota on mating and reproduction.