Khanty and Mansi are small indigenous peoples of Western Siberia with the unique cultural, anthropological, and linguistic characteristics. The study of their gene pool will make it possible to reconstruct the genetic structure of the Ugric-speaking population, of which in modern times only Khanty and Mansi remain, along with Hungarians, in whose gene pool there are traces of medieval migration of the Ugric-speaking Magyars. The detailed characterization of the gene pool of Khanty and Mansi is important for reconstruction of Ugric populations and genetic history of the region. The study was aimed to assess representative samples of Khants (n = 83) and Mansi (n = 74) based on the standard panel of 60 SNP markers and the extended panel of 74 Y-chromosomal SNP markers by statistical and cartographic methods in the context of indigenous population of Urals and Western Siberia. The differences between the gene pools of Khanty and Mansi have been revealed based on both standard panel of Y chromosome haplogroups and branches of haplogroups N2 and N3a4. Most of the Khanty gene pool is evenly distributed between N2-Y3195 (26%), N2-VL67 (23%), and N3a4-Z1936 (23%). The “Western” branch N2-Y3195 predominates in the Mansi gene pool (69%). Mansi gravitate towards populations of the Urals-Volga region in the multidimensional genetic space. Based on the standard panel of Y haplogroups, Khanty are close to the populations of Western and South Siberia. However, the analysis of branches N3a4 has shown that Khanty are intermediate between the “Uralic” and “Siberian” clusters: when the ancestors of Khanty moved from the Ural region to the northeast, these acquired both genetic components. The gene geographic maps of 10 haplogroup N3a4 branches in the populations of Urals and Western Siberia reflect the dynamic changes of the gene pool that took place 4–2 kya.