DNA barcoding based on mitochondrial (mt) nucleotide sequences is an enigma. Neutral models of mt evolution predict DNA barcoding cannot work for recently diverged taxa, and yet, mt DNA barcoding accurately delimits species for many bilaterian animals. Meanwhile, mt DNA barcoding often fails for plants and fungi. I propose that because mt gene products must cofunction with nuclear gene products, the evolution of mt genomes is best understood with full consideration of the two environments that impose selective pressure on mt genes: the external environment and the internal genomic environment. Moreover, it is critical to fully consider the potential for adaptive evolution of not just protein products of mt genes but also of mt transfer RNAs and mt ribosomal RNAs. The tight linkage of genes on mt genomes that do not engage in recombination could facilitate selective sweeps whenever there is positive selection on any element in the mt genome, leading to the purging of mt genetic diversity within a population and to the rapid fixation of novel mt DNA sequences. Accordingly, the most important factor determining whether or not mt DNA sequences diagnose species boundaries may be the extent to which the mt chromosomes engage in recombination.