Приходилось вновь начинать дело покорения; но на сей раз оно пошло легче и быстрее с помощью опыта и по проложенным путям. Окрестные остяки собрались вокруг русского городка и попытались взять его; но были отбиты. Тогда, по словам летописей, они принесли своего главного идола, пользовавшегося большим поклонением; поставили его под деревом и начали творить ему жертвы, прося помощи против христиан. Русские навели на него свою пушку; раздался выстрел, и дерево вместе с идолом было разбито в щепы. Остяки в страхе рассеялись и оставили русских в покое. Мало того, остяцкий князь Лугуй, который владел шестью городками по реке Оби, первый из местных владетелей отправился в Москву, где бил челом, чтобы государь принял его в число своих данников и не велел воевать его своим ратным людям, сидевшим на Усть-Иртыше. С ним обошлись ласково и наложили на него дань в семь сороков лучших соболей. Вслед за Мансуровым прибыли в Сибирскую землю воеводы Сукин и Мясной и начали с того, что на реке Туре, на месте старого городка Чингия, построили крепость Тюмень и в ней воздвигли христианский храм. А в следующем, 1587 году, после прибытия новых подкреплений, голова Данила Чуйков отправился из Тюмени далее, спустился по Тоболу до его устья и здесь на высоком берегу Иртыша основал Тобольск, в котором построил две церкви; этот город вскоре сделался средоточием русских владений в Сибири, благодаря своему выгодному положению в узле сибирских рек, то есть главных путей сообщения. Таким образом, вместо далеких и трудных походов первых завоевателей, московское правительство и здесь употребило обычную свою систему: распространять и упрочивать свое владычество на окраинах постепенным построением крепостей.

Тобольск явился неподалеку от прежнего средоточия Сибирского царства, то есть от города Сибирь. Такое соседство сильно стеснило татарского князя Сейдяка Бекбулатовича. Он попытался на открытую борьбу с русскими; собрал, сколько мог, войска и приступил к Тобольску. Но выстрелами из пищалей и пушек русские отразили приступы татар; а потом сделали вылазку и окончательно их разбили; причем сам Сейдяк был ранен и взят в плен. Этот бой замечателен еще тем, что в нем пал Матвей Мещеряк, последний из пяти известных атаманов. По другому известию, с Сейдяком покончили иным способом. Будто бы с одним киргиз-кайсацким царевичем и Карачой, бывшим Кучумовым вельможей, теперь перешедшим на сторону Сейдяка, сей последний задумал захватить Тобольск хитростью; для чего пришел с 500 человек и расположился на лугу подле города, под предлогом охоты. Догадываясь о его замысле, Чулков притворился его приятелем и пригласил его в гости, а также для переговоров о мире. Сейдяк с царевичем и Карачой вошел в город в сопровождении сотни своих татар, которых, однако, русские при въезде в город обезоружили. Во время пиршества, когда воевода пригласил своих гостей выпить за здоровье государя, те будто бы стали пить и поперхнулись. Тогда воевода объявил, что у них на уме недобрый замысел, и велел их схватить. После чего они были отправлены в Москву в 1588 году. (Полагают, что упомянутый здесь киргизский султан или царевич был не кто иной, как Ураз-Мухамед, который потом, в царствование Бориса Годунова, посажен ханом в Касимове.) После того стольный татарский город Сибирь был оставлен татарами и мало-помалу запустел.

Покончив с Сейдяком, русские воеводы принялись за Кучума, который оставался еще на свободе, кочевал в Барабинской степи и оттуда продолжал своими нападениями тревожить русских, упорно не признавая их владычества в своем бывшем ханстве. Он получал помощь от соседних ногаев, с князьями которых находился в близком свойстве, женив некоторых своих сыновей на их дочерях и выдав за них собственных дочерей. К нему же примкнула теперь и часть мурз осиротелого Тайбугина улуса. Летом 1591 года воевода князь Масальский ходил в Ишимскую степь близ озера Чили-Кула, разбил кучумовых татар и взял в плен его сына Абдул-Хаира. Но сам Кучум спасся и потом продолжал свои разбойничьи набеги. Чтобы обезопасить с этой стороны русские владения и стеснить движения Кучума, в 1594 году князь Андрей Елецкий с сильным отрядом двинулся вверх по Иртышу и близ впадения в него реки Тары заложил городок, названный именем этой реки. Новый город очутился почти в центре той плодородной и хорошо орошенной степи, по которой кочевала орда Кучума, угрозами и насилием собирая ясак с татарских волостей, расположенных по Иртышу и уже присягнувших на русское подданство. Город Тара действительно оказал большую пользу в борьбе с ним. Отсюда русские неоднократно предпринимали против него поиски в степи; били его татар, разоряли его улусы, перехватывали шедших к нему гонцов и торговцев, ногайских и бухарских, вступали в сношения с его мурзами, которых подарками и обещаниями льгот переманивали в наше подданство. При сем воеводы не раз посылали к нему с увещаниями, чтобы он прекратил свое сопротивление и покорился русскому государю, обнадеживая его царскими милостями. От самого царя Федора Ивановича отправлена была к нему увещательная грамота: она указывала на его безвыходное положение, на то, что два его сына в плену, друзья его оставили, Сибирь покорена, что сам Кучум сделался бездомным казаком, что государю стоит только послать на него свою большую рать, чтобы его уничтожить; но что государь готов все забыть, если Кучум явится в Москву с повинной; тогда в награду ему даны будут города и волости, а если пожелает, то и прежний его юрт, то есть самая Сибирь. Пленный Абдул-Хаир, по внушению московского правительства, также писал отцу и склонял его покориться, приводя в пример себя и брата Магметкула, которым государь пожаловал города и волости (в кормление). Ничто, однако, не могло склонить упрямого старика к покорности. В своих ответах он бьет челом Белому царю, чтобы тот отдал ему назад иртышский берег, а воевод русских просит воротить ему один конский вьюк, захваченный ими вместе с шедшими к нему послами; в этом вьюке находилось зелье для его больных глаз. С самого прихода Ермака он борется с русскими и Сибири им не отдавал: сами взяли. Помириться он готов, но только «правдою». И к этому он еще прибавляет наивную угрозу: «С ногаями я в союзе, и если с двух сторон станем, то плохо будет московскому владению».

Решили во что бы то ни стало покончить с упрямым, беспокойным стариком. В августе 1598 года воевода Воейков выступил из Тары в Барабинскую степь с отрядом в 400 человек казаков