The tribe Bovini contains a number of commercially and culturally important species, such as cattle. Understanding their evolutionary time scale is important for distinguishing between post-glacial and domestication-associated population expansions, but estimates of bovine divergence times have been hindered by a lack of reliable calibration points. We present a Bayesian phylogenetic analysis of 481 mitochondrial D-loop sequences, including 228 radiocarbon-dated ancient DNA sequences, using a multi-demographic coalescent model. By employing the radiocarbon dates as internal calibrations, we co-estimate the bovine phylogeny and divergence times in a relaxed-clock framework. The analysis yields evidence for significant population expansions in both taurine and zebu cattle, European aurochs and yak clades. The divergence age estimates support domestication-associated expansion times (less than 12 kyr) for the major haplogroups of cattle. We compare the molecular and palaeontological estimates for the Bison-Bos divergence.