Ancient cattle bones were excavated from archaeological sites in Jeju, Korea. We used molecular genetic techniques to identify the species and establish its relationship to extant cattle breeds. Ancient DNA was extracted from four sources: a humerus (Gonae site, A.D. 700-800), two fragments of radius, and a tooth (Kwakji site, A.D. 0-900). The mitochondrial DNA (mtDNA) D-loop regions were cloned, sequenced, and compared with previously reported sequences of various cattle breeds (9 Asian, 8 European, and 3 African). The results revealed that these bones were of the breed, Bos taurus, and a phylogenetic tree indicated that the four cattle bones formed a monophyletic group with Jeju native black cattle. However, the patterns of sequence variation and reports from archaeological sites suggest that a few wild cattle, with a different maternal lineage, may have existed on Jeju Island. Our results will contribute to further studies of the origin of Jeju native cattle and the possible existence of local wild cattle.