We have analyzed Y-chromosomal variation in populations from Transoxiana, a historical region covering the southwestern part of Central Asia. We studied 780 samples from 10 regional populations of Kazakhs, Uzbeks, Turkmens, Dungans, and Karakalpaks using 35 SNP and 17 STR markers. Analysis of haplogroup frequencies using multidimensional scaling and principal component plots, supported by an analysis of molecular variance, showed that the geographic landscape of Transoxiana, despite its distinctiveness and diversity (deserts, fertile river basins, foothills and plains) had no strong influence on the genetic landscape. The main factor structuring the gene pool was the mode of subsistence: settled agriculture or nomadic pastoralism. Investigation of STR-based clusters of haplotypes and their ages revealed that cultural and demic expansions of Transoxiana were not closely connected with each other. The Arab cultural expansion introduced Islam to the region but did not leave a significant mark on the pool of paternal lineages. The Mongol expansion, in contrast, had enormous demic success, but did not impact cultural elements like language and religion. The genealogy of Muslim missionaries within the settled agricultural communities of Transoxiana was based on spiritual succession passed from teacher to disciple. However, among Transoxianan nomads, spiritual and biological succession became merged.