Although a large part of the global domestic dog population is free-ranging and free-breeding, knowledge of genetic diversity in these free-breeding dogs (FBDs) and their ancestry relations to pure-breed dogs is limited, and the indigenous status of FBDs in Asia is still uncertain. We analyse genome-wide SNP variability of FBDs across Eurasia, and show that they display weak genetic structure and are genetically distinct from pure-breed dogs rather than constituting an admixture of breeds. Our results suggest that modern European breeds originated locally from European FBDs. East Asian and Arctic breeds show closest affinity to East Asian FBDs, and they both represent the earliest branching lineages in the phylogeny of extant Eurasian dogs. Our biogeographic reconstruction of ancestral distributions indicates a gradual westward expansion of East Asian indigenous dogs to the Middle East and Europe through Central and West Asia, providing evidence for a major expansion that shaped the patterns of genetic differentiation in modern dogs. This expansion was probably secondary and could have led to the replacement of earlier resident populations in Western Eurasia. This could explain why earlier studies based on modern DNA suggest East Asia as the region of dog origin, while ancient DNA and archaeological data point to Western Eurasia.