Many bacteria live on host surfaces, in cells and in specific organ systems. In comparison with gut microbiomes, the bacterial communities of reproductive organs (genital microbiomes) have received little attention. During mating, male and female genitalia interact and copulatory wounds occur, providing an entrance for sexually transmitted microbes. Besides being potentially harmful to the host, invading microbes might interact with resident genital microbes and affect immunity. Apart from the investigation of sexually transmitted symbionts, few studies have addressed how mating changes genital microbiomes. We dissected reproductive organs from virgin and mated common bedbugs, Cimex lectularius L., and sequenced their microbiomes to investigate composition and mating-induced changes. We show that mating changes the genital microbiomes, suggesting bacteria are sexually transmitted. Also, genital microbiomes varied between populations and the sexes. This provides evidence for local and sex-specific adaptation of bacteria and hosts, suggesting bacteria might play an important role in shaping the evolution of reproductive traits. Coadaptation of genital microbiomes and reproductive traits might further lead to reproductive isolation between populations, giving reproductive ecology an important role in speciation. Future studies should investigate the transmission dynamics between the sexes and populations to uncover potential reproductive barriers.