African elephant mitochondrial (mt) DNA follows a distinctive evolutionary trajectory. As females do not migrate between elephant herds, mtDNA exhibits low geographic dispersal. We therefore examined the effectiveness of mtDNA for assigning the provenance of African elephants (or their ivory). For 653 savanna and forest elephants from 22 localities in 13 countries, 4258 bp of mtDNA was sequenced. We detected eight mtDNA subclades, of which seven had regionally restricted distributions. Among 108 unique haplotypes identified, 72% were found at only one locality and 84% were country specific, while 44% of individuals carried a haplotype detected only at their sampling locality. We combined 316 bp of our control region sequences with those generated by previous trans-national surveys of African elephants. Among 101 unique control region haplotypes detected in African elephants across 81 locations in 22 countries, 62% were present in only a single country. Applying our mtDNA results to a previous microsatellite-based assignment study would improve estimates of the provenance of elephants in 115 of 122 mis-assigned cases. Nuclear partitioning followed species boundaries and not mtDNA subclade boundaries. For taxa such as elephants in which nuclear and mtDNA markers differ in phylogeography, combining the two markers can triangulate the origins of confiscated wildlife products.