The geographic and temporal origins of the domestic dog remain controversial, as genetic data suggest a domestication process in East Asia beginning 15,000 years ago, whereas the oldest doglike fossils are found in Europe and Siberia and date to >30,000 years ago. We analyzed the mitochondrial genomes of 18 prehistoric canids from Eurasia and the New World, along with a comprehensive panel of modern dogs and wolves. The mitochondrial genomes of all modern dogs are phylogenetically most closely related to either ancient or modern canids of Europe. Molecular dating suggests an onset of domestication there 18,800 to 32,100 years ago. These findings imply that domestic dogs are the culmination of a process that initiated with European hunter-gatherers and the canids with whom they interacted.