The domestication of cattle is generally accepted to have taken place in two independent centres: around 10,500 years ago in the Near East, giving rise to modern taurine cattle, and two millennia later in southern Asia, giving rise to zebu cattle. Here we provide firmly dated morphological and genetic evidence for early Holocene management of taurine cattle in northeastern China. We describe conjoining mandibles from this region that show evidence of oral stereotypy, dated to the early Holocene by two independent (14)C dates. Using Illumina high-throughput sequencing coupled with DNA hybridization capture, we characterize 15,406 bp of the mitogenome with on average 16.7-fold coverage. Phylogenetic analyses reveal a hitherto unknown mitochondrial haplogroup that falls outside the known taurine diversity. Our data suggest that the first attempts to manage cattle in northern China predate the introduction of domestic cattle that gave rise to the current stock by several thousand years.