Background: Woolly rhinoceros (Coelodonta antiquitatis) is a typical indicator of cold-stage climate that was widely distributed in Northern Hemisphere during the Middle-Late Pleistocene. Although a plethora of fossils have been excavated from Northern China, their phylogenetic status, intraspecific diversity and phylogeographical structure are still vague. Results: In the present study, we generated four mitogenomes from Late Pleistocene woolly rhinoceros in Northern China and compared them with published data. Bayesian and network analyses indicate that the analyzed individuals contain at least four maternal haplogroups, and Chinese samples fall in three of them. One of our samples belongs to a previously unidentified early diverging clade (haplogroup D), which separated from other woolly rhinoceros around 0.57 Ma (95% CI: 0.76–0.41 Ma). The timing of this clade’s origin coincides with the first occurrence of woolly rhinoceros, which are thought to have evolved in Europe. Our other three samples cluster in haplogroup C, previously only identified from one specimen from Wrangel Island (ND030) and initially considered to be an isolated clade. Herein, our findings suggest that ND030 is likely descended from a northward dispersal of the individuals carrying haplogroup C from Northern China. Additionally, Chinese woolly rhinoceros specimens exhibit higher nucleotide diversity than those from Siberia. Conclusion: Our findings highlight Northern China as a possible refugium and a key evolution center of the Pleistocene woolly rhinoceros.