The tRNAleu-COX2 intergenic region of the mitochondrial DNA has been used for assessing diversity in honey bee (Apis mellifera L.) populations worldwide. However, differential mutation rates in different partitions of the mitogenome may produce incongruent results. In this study, we sequenced 123 mitogenomes of 7 subspecies from lineages A, M, and C. This allowed generating a comprehensive dataset to investigate the phylogenetic and phylogeographic congruence among the mitogenome, individual genes, and the tRNAleu-COX2 region. We showed that the diversity patterns inferred from the tRNAleu-COX2 marker are not fully paralleled by those obtained with the mitogenome and the individual genes; while the three lineages are supported by these, the African sub-lineages and the haplotypes are not. Thus, conclusions drawn from the tRNAleu-COX2 region need to be taken with caution and this marker may not be appropriate to infer phylogenetic relationships between honey bee colonies.