Infections with maternally inherited Wolbachia bacteria may have dramatic influences on reproductive traits and speciation patterns of their hosts. We here show that in the beetle genus Altica, infection has influenced phylogenetic patterns of the host’s mtDNA and different strains led to repeated selective sweeps. By comparing a COI/II based phylogeny of the hosts with a phylogeny of the bacteria based on ftsZ, we show that co-speciation is rare and restricted to few recently diverged...