The gray wolf (Canis lupus) is a widely distributed top predator and ancestor of the domestic dog. The specific evolutionary relationships of dogs and extant wolves are controversial and have been explored with a variety of genomic approaches. However, these studies suffer from a paucity of samples from throughout the Holarctic range of the wolf. To address questions about wolf relationships to each other and dogs, we assemble and analyze a dataset of 34 canine genomes. The divergence between New and Old World wolves is the earliest branching event, and is followed by the divergence of Old World wolves and dogs, confirming that the dog was domesticated in the Old World. However, no single wolf population is more closely related to dogs, supporting the hypothesis that dogs were derived from an extinct wolf population. All extant wolves have a surprising recent common ancestry, and experienced a dramatic population decline beginning at least ~30 kya. We suggest this crisis was related to the colonization of Eurasia by modern human hunter-gatherers who competed with wolves for limited prey but also domesticated them, leading to a compensatory population expansion of dogs. We found extensive admixture between dogs and wolves, with up to 25% of Eurasian wolf genomes showing signs of dog ancestry. Dogs have influenced the recent history of wolves through admixture and vice versa, potentially enhancing adaptation. Simple scenarios of dog domestication are confounded by admixture, and studies that do not take admixture into account with specific demographic models are problematic.