Despite numerous investigations leveraging both genetic and archaeological evidence, the geographic origins of dogs remain unknown. On the basis of an ancient Irish dog genome and an assessment of the spatiotemporal appearance of dogs in the archaeological record, a recent paper suggested that dogs may have been domesticated independently in Eastern and Western Eurasia from distinct wolf populations. Following those independent origins, a mitochondrial assessment suggested that the Mesolithic dog population in Western Europe may have been replaced by a population from the East. To test these and other hypotheses, we are generating nuclear genomes from ancient dog remains from sites across the Northern Hemisphere, and mitochondrial genomes from ~1000 dogs spanning the last 15,000 years. The results of these analyses are revealing the ancestral affinities of dogs that were present across the Old World and we are beginning to understand the the timings and movements of dog populations through time and space. The combination of an archaeological time depth with the resolution of whole genomes is allowing us to reveal the history of our longest and fondest domestic partner.