Northwest Siberia is geographically remote territory, which has been settled by indigenous human populations probably since the Upper Paleolithic. To investigate the genetic landscape of Northwest Siberians, we have analyzed mitochondrial and Y chromosome DNA polymorphisms of 169 unrelated individuals from Khanty and Mansi ethnic groups in Northwest Siberia. In addition, HVS-I sequences (N = 3522) and Y chromosome SNP data (N = 2175), obtained from the literature, were used to elucidate the genetic relationships among the North Eurasian populations. The results show clinal distributions of mtDNA and Y chromosome haplogroups along East-West axis of Northern Eurasia. In this context, the Ugric-speaking Khanty and Mansi appear as unique intermediate populations carrying Upper Paleolithic and more recent haplotypes typical for both West and East Eurasian gene pools. This admixture indicates that the Khanty and Mansi populations have resided in the contact zone of genetically distinguishable eastern and western Eurasia.