The swamp type of the Asian water buffalo is assumed to have been domesticated by about 4000 years BP, following the introduction of rice cultivation. Previous localizations of the domestication site were based on mitochondrial DNA (mtDNA) variation within China, accounting only for the maternal lineage. We carried out a comprehensive sampling of China, Taiwan, Vietnam, Laos, Thailand, Nepal and Bangladesh and sequenced the mtDNA Cytochrome b gene and control region and the Y-chromosomal ZFY, SRY and DBY sequences. Swamp buffalo has a higher diversity of both maternal and paternal lineages than river buffalo, with also a remarkable contrast between a weak phylogeographic structure of river buffalo and a strong geographic differentiation of swamp buffalo. The highest diversity of the swamp buffalo maternal lineages was found in South China and North Indochina on both banks of the Mekong River, while the highest diversity in paternal lineages was in the China-Indochina border region. We propose that domestication in this region was later followed by introgressive capture of wild cows west of the Mekong. Migration to the north followed the Yangtze valley as well as a more eastern route, but also involved translocations of both cows and bulls over large distances with a minor influence of river buffaloes in recent decades. Bayesian analyses of various migration models also supported domestication in the China-Indochina border region. Coalescence analysis yielded consistent estimates for the expansion of the major swamp buffalo haplogroups with a credibility interval of 900 to 3,900 years BP. The spatial differentiation of mtDNA and Y-chromosomal haplotype distributions indicates a lack of gene flow between established populations that is unprecedented in livestock.