The origin of domestic dogs is poorly understood [1-15], with suggested evidence of dog-like features in fossils that predate the Last Glacial Maximum [6, 9, 10, 14, 16] conflicting with genetic estimates of a more recent divergence between dogs and worldwide wolf populations [13, 15, 17-19]. Here, we present a draft genome sequence from a 35,000-year-old wolf from the Taimyr Peninsula in northern Siberia. We find that this individual belonged to a population that diverged from the common ancestor of present-day wolves and dogs very close in time to the appearance of the domestic dog lineage. We use the directly dated ancient wolf genome to recalibrate the molecular timescale of wolves and dogs and find that the mutation rate is substantially slower than assumed by most previous studies, suggesting that the ancestors of dogs were separated from present-day wolves before the Last Glacial Maximum. We also find evidence of introgression from the archaic Taimyr wolf lineage into present-day dog breeds from northeast Siberia and Greenland, contributing between 1.4% and 27.3% of their ancestry. This demonstrates that the ancestry of present-day dogs is derived from multiple regional wolf populations.