Rates of mitogenome evolution differ among animal lineages, and this variation has been linked to life history, ecological traits, and— potentially—to sex-determination system. Insects are a strong model for examining the latter factor because haplodiploidy (HD) has evolved on multiple occasions from a diplodiploid (DD) ancestral state. We tested for rate differences between DD and HD taxa by examining sequence change in a sentinel segment of the mitogenome, the 658 bp barcode region of the cytochrome c oxidase I (COI) gene. Specifically, we investigated if amino acid substitutions and indels are more frequent in HD than DD lineages by inspecting COI sequences from over 86,000 BINs (a species proxy) representing 783 insect families and 26 orders. Among them, ten lineages, varying in rank from tribe to order, are HD. Our analysis, which accounts for phylogeny, indicates that HD lineages have higher rates (1.7×) of amino acid substitution, higher Ka/Ks (3.5×), and far more indels than DD taxa. While our results demonstrate that HD accelerates mitogenome evolution, future work needs to clarify its mechanistic basis. We hypothesize that HD facilitates positive selection for mitochondrial mutations which encode proteins that interact with nuclear gene products. Such coevolutionary interactions should be facilitated because recessive mutations in the nuclear genome are fully exposed to selection in males of HD but not DD lineages.