There is no generally accepted picture of where, when, and how the domestic dog originated. Previous studies of mitochondrial DNA (mtDNA) have failed to establish the time and precise place of origin because of lack of phylogenetic resolution in the so far studied control region (CR), and inadequate sampling. We therefore analyzed entire mitochondrial genomes for 169 dogs to obtain maximal phylogenetic resolution and the CR for 1,543 dogs across the Old World for a comprehensive picture of geographical diversity. Hereby, a detailed picture of the origins of the dog can for the first time be suggested. We obtained evidence that the dog has a single origin in time and space and an estimation of the time of origin, number of founders, and approximate region, which also gives potential clues about the human culture involved. The analyses showed that dogs universally share a common homogenous gene pool containing 10 major haplogroups. However, the full range of genetic diversity, all 10 haplogroups, was found only in southeastern Asia south of Yangtze River, and diversity decreased following a gradient across Eurasia, through seven haplogroups in Central China and five in North China and Southwest (SW)Asia, down to only four haplogroups in Europe. The mean sequence distance to ancestral haplotypes indicates an origin 5,400–16,300 years ago (ya) from at least 51 female wolf founders. These results indicate that the domestic dog originated in southern China less than 16,300 ya, from several hundred wolves. The place and time coincide approximately with the origin of rice agriculture, suggesting that the dogs may have originated among sedentary hunter-gatherers or early farmers, and the numerous founders indicate that wolf taming was an important culture trait.