Dogs were the first domestic animal, but little is known about their population history and to what extent it was linked to humans. We sequenced 27 ancient dog genomes and found that all dogs share a common ancestry distinct from present-day wolves, with limited gene flow from wolves since domestication but substantial dog-to-wolf gene flow. By 11,000 years ago, at least five major ancestry lineages had diversified, demonstrating a deep genetic history of dogs during the Paleolithic. Coanalysis with human genomes reveals aspects of dog population history that mirror humans, including Levant-related ancestry in Africa and early agricultural Europe. Other aspects differ, including the impacts of steppe pastoralist expansions in West and East Eurasia and a near-complete turnover of Neolithic European dog ancestry.