The spread of maternally inherited microorganisms, such as Wolbachia bacteria, can induce indirect selective sweeps on host mitochondria, to which they are linked within the cytoplasm. The resulting reduction in effective population size might lead to smaller mitochondrial diversity and reduced efficiency of natural selection. While documented in several host species, it is currently unclear if such a scenario is common enough to globally impact the diversity and evolution of mitochondria in Wolbachia-infected lineages. Here, we address this question using a mapping of Wolbachia acquisition/extinction events on a large mitochondrial DNA tree, including over 1000 species. Our analyses indicate that on a large phylogenetic scale, other sources of variation, such as mutation rates, tend to hide the effects of Wolbachia. However, paired comparisons between closely related infected and uninfected taxa reveal that Wolbachia is associated with a twofold reduction in silent mitochondrial polymorphism, and a 13% increase in nonsynonymous substitution rates. These findings validate the conjecture that the widespread distribution of Wolbachia infections throughout arthropods impacts the effective population size of mitochondria. These effects might in part explain the disconnection between genetic diversity and demographic population size in mitochondria, and also fuel red-queen-like cytonuclear co-evolution through the fixation of deleterious mitochondrial alleles.