Technical Abstract: Background: Complete mitochondrial genome sequences have become important tools for the study of genome architecture, phylogeny, and molecular evolution. Despite the rapid increase in available mitogenomes, the taxonomic sampling often poorly reflects phylogenetic diversity and is often also biased to represent deeper (family-level) evolutionary relationships. Results: We present the first fully sequenced ant (Hymenoptera: Formicidae) mitochondrial genomes. We sampled four mitogenomes from three species of fire ants, genus Solenopsis, which represent various evolutionary depths. Overall, ant mitogenomes appear to be typical of hymenopteran mitogenomes, displaying a general A+T-bias. The Solenopsis mitogenomes are slightly more compact than other hymentoperan mitogenomes (~15.5kb), retaining all protein coding genes and ribosomal RNAs. The only structural differences are found in the number and placement of tRNAs. We also present evidence of recombination between the mitogenomes of the most closely related Solenopsis study species (richteri and invicta). Finally, we discuss potential ways to improve the estimation of phylogenies using complete mitochondrial genome sequences. Conclusions: Since the Solenopsis mitogenomes are so closely related yet still display variation in tRNA gene order and evidence of recombination, we suggest that mitochondrial tRNA gene rearrangements may be too evolutionarily labile to be of much use as phylogenetic markers at great phylogenetic depths. We also discuss ways that may help improve the use of mitogenomes in phylogenetic analyses by accounting for nonstationary and non-homogeneous evolution between branches.