Northwestern China, an important part of the Silk Road, was the birthplace of the Zhouzu farming culture. The domestication of cattle as an important aspect of farming culture has had a long history in northwestern China. In this study, we assessed the maternal structure and phylogeny of cattle by analyzing the mitochondrial DNA hypervariable segment I (HVS-I) in 698 native cattle from eight areas of northwestern China. The phylogenetic analyses revealed two highly divergent mtDNA clades: clade T, which had four sub-clades (Ta-Td), and clade I. The cattle domesticated from Bos taurus showed a clear dominant distribution pattern in northwestern China. The nucleotide diversity of the Bos indicus clade was lower than that of clades from Bos taurus. In summary, our results suggest that the native cattle of northwestern China were domesticated from two different maternal ancestors, Bos taurus and Bos indicus, which migrated to the central plains of China from the north and south, respectively, with Bos taurus remaining at the edges of the region. The population expansion of the cattle domesticated from Bos taurus occurred in the Longdong region of Gansu Province, and these cattle formed four relatively independent evolutionary branches. Subsequent to this expansion event, Bos indicus migrated from southern to northern China.