There were several species of Equus in northern China during the Late Pleistocene, including Equus przewalskii and Equus dalianensis. A number of morphological studies have been carried out on E. przewalskii and E. dalianensis, but their evolutionary history is still unresolved. In this study, we retrieved near-complete mitochondrial genomes from E. dalianensis and E. przewalskii specimens excavated from Late Pleistocene strata in northeastern China. Phylogenetic analyses revealed that caballoid horses were divided into two subclades: the New World and the Old World caballine horse subclades. The Old World caballine horses comprise of two deep phylogenetic lineages, with modern and ancient Equus caballus and modern E. przewalskii forming lineage Ⅰ, and the individuals in this study together with one Yakut specimen forming lineage Ⅱ. Our results indicate that Chinese Late Pleistocene caballoid horses showed a closer relationship to other Eurasian caballine horses than that to Pleistocene horses from North America. In addition, phylogenetic analyses suggested a close relationship between E. dalianensis and the Chinese fossil E. przewalskii, in agreement with previous researches based on morphological analyses. Interestingly, E. dalianensis and the fossil E. przewalskii were intermixed rather than split into distinct lineages, suggesting either that gene flow existed between these two species or that morphology-based species assignment of palaeontological specimens is not always correct. Moreover, Bayesian analysis showed that the divergence time between the New World and the Old World caballoid horses was at 1.02 Ma (95% CI: 0.86–1.24 Ma), and the two Old World lineages (Ⅰ & Ⅱ) split at 0.88 Ma (95% CI: 0.69–1.13 Ma), which indicates that caballoid horses seem to have evolved into different populations in the Old World soon after they migrated from North America via the Bering Land Bridge. Finally, the TMRCA of E. dalianensis was estimated at 0.20 Ma (95% CI: 0.15–0.28 Ma), and it showed a relative low genetic diversity compared with other Equus species.