Historical records suggest that horses inhabiting the island of Cheju in Korea are descendants of Mongolian horses introduced in 1276. Other studies, however, suggest that horses may have been present on the island prior to the Mongolian introduction. To determine the origin of the Cheju horses we used a phylogenetic analysis of sequences of the mitochondrial DNA (mtDNA) D-loop region, including tRNA Pro and parts of tRNA thr and tRNA Phe sequences (1102-bp excluding the tandem repeat region). Maximum parsimony and neighbor-joining trees were constructed using sequences determined for seven Cheju, four Mongolian, one Przewalskii and two Chinese Yunnan horses, and published sequences for one Swedish and three Thoroughbred horses. Donkey mtDNA was used as an outgroup. We found that the mtDNA D-loop sequence varies considerably within Mongolian, Cheju and Thoroughbred horse breeds, and that Cheju horses clustered with Mongolian horses as well as with horses from other distantly related breeds. On the basis of these findings we propose that horses on Cheju Island are of mixed origin in their maternal lineage, and that horses may have existed and been traded on the island before the Mongolian introduction.