Построив в 1593 году городок Берёзов, русские закрепились в низовьях Оби. На следующее лето русское правительство планировало наступление вверх по реке от места слияния её с Иртышом, где стоял в то время Обский городок. Воеводам князю Фёдору Барятинскому и Владимиру Аничкову приказано было зимой прибыть в Лозьвинский городок, а по вскрытии рек плыть на судах в Обский город через Пелым и Тобольск, пополнив свой отряд служилыми людьми этих городов. В Обском городе к ним присоединились служилые люди из Берёзова и остяки князя Игичея. Объединённая рать поплыла вверх по Оби, чтобы построить город в остяцкой земле «в котором месте пригоже». Город Сургут был поставлен на правом берегу Оби при впадении в неё речки Сургутки, в центре земли, подвластной хантыйскому князю Бардаку, принявшему русское подданство. Для усиления Сургутского гарнизона в него были включены служилые люди Обского городка, который был сломан и прекратил своё существование.
Как и другие сибирские остроги, Сургут представлял собою небольшую деревянную крепость с двумя воротами, пятью башнями (четыре глухие и одна проезжая); воеводский двор, тюрьма, церковь, государевы амбары, дома служилых людей, пороховой погреб. Всё это построено было в одно лето 1594 года. Несколько позднее появился Гостиный двор. Гарнизон Сургута составлял около 150 служилых людей. К Сургутскому уезду отошли земли вверх и вниз по Оби до слияния её с Иртышом.
После основания Сургута началось активное продвижение русских отрядов и промышленников верх по Оби. Здесь русские оказались в соседстве с объединением племён или родов под названием «Пегая орда» (селькупы). Во главе союза «Пегой орды» стоял князь Воня, союзник Кучума. Для покорения Пегой Орды в наказе воеводам предписывалось: «Вонина сына Урунка взять с собой в новый город, и к отцу его приказать, чтобы он был в новый город в Сургут и ясак с себя и с своей братии Пегой орды собрал и привёз к вам. А государь его пожаловал, велел отдать ему его сына и велел держать его под своей высокой рукой. Буде сам Воня в новый город не будет, а пришлёт ясак с племянником или с лучшими людьми и им ясак взять и сына Вонина отпустить к отцу. Если же Воня ясак не пришлёт и им, собрав людей, Пегую Орду воевать, чтобы Воню извоевать, ясак взять и привести под государеву руку.»
Воня прислал ясак, чтобы выручить из плена своего сына в 1594 году. Но покоряться он не собирался. У Вони было до 400 воинов, с которыми он намеревался уничтожить Сургут в союзе с Кучумом. Сургутский воевода доносил: «Сказывал князь Бардак, что царь Кучум подкочевал к Пегой Орде, ссылается с князем Воней, и что они постановили меж собой договор, чтоб весною со всеми своими людьми идти против Сургута…».
Московское правительство отнеслось к вестям о враждебных приготовлениях Пегой Орды очень серьёзно. Для похода на князя Воню весной 1597 года в Сургуте были собраны весьма значительные для Сибири силы: 50 служилых людей и сотня татар из Тобольска, 50 служилых из Берёзова и сотня остяков князя Игичея. К этим трём сотням сургутскому воеводе предписывалось добавить 100 человек служилых из Сургута и 150 остяков, от которых нельзя ждать измены. Общая численность войска составляла 550 человек. Наказ предписывал войску двигаться бережно, чтобы Воня не проведал о походе. А прибыв в землю Пегой орды сначала поставить острог, а затем уже действовать против неприятеля «сколько Бог помощи подаст», чтобы непременно привести Пегую орду под царскую руку. Обстоятельства похода описаны в челобитной его участников, кодских остяков: «Их же остяков 300 человек посылали на государеву службу вверх по Оби реке в Пегую орду под Нарымский городок с Иваном с Каляминовым и со князем Петром и со князь Иваном Алачовыми и с русскими служилыми людьми войною… Нарымский городок взяли и на бою многих изменников остяков побили, а жён их и детей в полон поимали».
Таким образом, в результате похода Пегая орда была разгромлена и покорена. Русские построили здесь Нарымский острог (1597), ставший опорным пунктом русской власти в Нарымском крае. О князе Воне более в документах не упоминается. Служилые люди захватили в походе на Пегую орду множество пленных. Об их дальнейшей судьбе говорится в царской грамоте сургутскому воеводе. Царь приказывал воеводе отобрать у служилых пленников и тех, которые не крещены, отослать на родину, а крещёных мужчин поверстать в службу, жёнок и девок выдать замуж за служивых людей, малых ребят поверстать в службу, когда подрастут. Но чтобы никто не смел пленных вывозить на Русь под страхом смертной казни.
В связи с покорением Пегой орды гарнизон Сургута в ближайшие годы значительно увеличился, достигнув в 1601 году 280 человек служилых людей: казаков, стрельцов, литвы и черкас. Не все они несли службу в Сургуте. С построением Нарымского и Кетского острогов из сургутского гарнизона посылались туда годовальщики по 20 человек в каждый острог. Затем, с появлением в Сибири всё новых городов, численность сургутского гарнизона стала постепенно сокращаться вместе с уменьшением его военного значения.