Archaeozoological and genetic data indicate that taurine cattle were first domesticated from local wild ox (aurochs) in the Near East some 10,500 years ago. However, while modern mitochondrial DNA (mtDNA) variation indicates early Holocene founding event(s), a lack of ancient DNA data from the region of origin, variation in mutation rate estimates, and limited application of appropriate inference methodologies have resulted in uncertainty on the number of animals first domesticated. A large number would be expected if cattle domestication was a technologically straightforward and unexacting region-wide phenomenon, while a smaller number would be consistent with a more complex and challenging process. We report mtDNA sequences from 15 Neolithic to Iron Age Iranian domestic cattle and, in conjunction with modern data, use serial coalescent simulation and approximate Bayesian computation to estimate that around 80 female aurochs were initially domesticated. Such a low number is consistent with archaeological data indicating that initial domestication took place in a restricted area and suggests the process was constrained by the difficulty of sustained managing and breeding of the wild progenitors of domestic cattle.