Na początku XVI w. ziemie Jugry zajęte zostały przez Tatarów i wchodziły w skład Chanatu Syberyjskiego. Stanowiły one jedną z ważniejszych części tego państwa.
W 1555 r. Rosja ponownie rozciągnęła nad Jugrą władzę zwierzchnią, gdyż władca Chanatu Syberyjskiego stał się wasalem carów rosyjskich. Wyrazem owej podległości była m.in. coroczna danina płacona w skórach sobolich, pozyskiwanych w dużej części na terenie Jugry. Gdy w 1563 r. chan Kuczum zerwał ową zależność i najechał ziemie cara, odwetowe wyprawy rosyjskie rozbiły chanat, a jedna z nich, pod dowództwem Jermaka, w 1582 r. ostatecznie przyłączyła większość terenu Chanty-Mansyjskiego OA do Rosji. Reszta terytorium została przyłączona wkrótce potem, do końca XVI w.
Kolonizacja rosyjska thumb|Mapa fragmentu ziem okręgu z 1701 r.
Wkrótce po przyłączeniu tych ziem rozpoczęła się rosyjska kolonizacja Jugry: w 1593 r. na miejscu starego chantyjskiego grodu Sugmut-Basz, inaczej zwanego Chałumo-Sugmut co w przekładzie oznacza „brzozowy gródek” założono pierwsze rosyjskie miasto Bieriozow, obecnie Bieriozowo, a w 1594 r. założono miasto Surgut – obecnie największe skupisko ludności w Okręgu. Intensywne osadnictwo rosyjskie rozpoczęło się jednak dopiero w połowie, a nasiliło w końcu XVII w.