In order to investigate the genetic history of autochthonous South Siberian populations and to estimate the contribution of distinct patrilineages to their gene pools, we have analyzed 17 Y-chromosomal binary markers (YAP, RPS4Y(711), SRY-8299, M89, M201, M52, M170, 12f2, M9, M20, 92R7, SRY-1532, DYS199, M173, M17, Tat, and LLY22 g) in a total sample of 1,358 males from 14 ethnic groups of Siberia (Altaians-Kizhi, Teleuts, Shors, Tuvinians, Todjins, Tofalars, Sojots, Khakassians, Buryats, Evenks), Central/Eastern Asia (Mongolians and Koreans) and Eastern Europe (Kalmyks and Russians). Based on both, the distribution pattern of Y-chromosomal haplogroups and results on AMOVA analysis we observed the statistically significant genetic differentiation between the populations of Baikal and Altai-Sayan regions. We suggest that these regional differences can be best explained by different contribution of Central/Eastern Asian and Eastern European paternal lineages into gene pools of modern South Siberians. The population of the Baikal region demonstrates the prevalence of Central/Eastern Asian lineages, whereas in the populations of Altai and Sayan regions the highest paternal contribution resulted from Eastern European descent is revealed. Yet, our data on Y-chromosome STRs variation demonstrate the clear differences between the South Siberian and Eastern European R1a1-lineages with the evolutionary ages compatible with divergence time between these two regional groups.