Western Kazakhstan is populated by three clans totaling 2 million people. Since the clans are patrilineal, the Y-chromosome is the most informative genetic system for tracing their origin. We genotyped 40 Y-SNP and 17 Y-STR markers in 330 Western Kazakhs. High phylogenetic resolution within haplogroup C2a1a2-M48 was achieved by using additional SNPs. Three lines of evidence indicate that the Alimuly and Baiuly clans (but not the Zhetiru clan) have a common founder placed 700 ± 200 years back by the STR data and 500 ± 200 years back by the sequencing data. This supports traditional genealogy claims about the descent of these clans from Emir Alau, who lived 650 years ago and whose lineage might be carried by two-thirds of Western Kazakhs. There is accumulation of specific haplogroups in the subclans representing other lineages, confirming that the clan structure corresponds with the paternal genetic structure of the steppe population.