Однако, подслеповатость не помешала Кучуму объявиться однажды в окрестностях Тобольска. Это было через три года после основания города. И тогда, в начале 1590 года, правительство послало в Тобольск испытанного военоначальника и дипломата князя Владимира Васильевича Мосальского-Кольцова. (Это, собственно, и был первый воевода тобольский. До тех пор Тобольск находился в ведении тюменских воевод). Явившись на смену основателю города Даниле Чулкову, князь Владимир должен был сразу же оборонять город. Кучум грабил окрестности, уничтожая русские селенья и селенья признавших русскую власть татар. Князь Владимир прогнал орду, но вскоре нападение повторилось. И опытный военоначальник князь Владимир Мосальский понял, что маленький, состоящий, из пятисот человек гарнизон Тобольска едва ли сможет противостоять всей Сибири татарской. Но недаром князь Владимир считался не только полководцем, а и мудрым политиком. Годунов знал, кого он посылает в Сибирь. Участник литовского похода, человек, сумевший когда-то собрать под русские знамена жителей Прибалтики, энергичный организатор, князь Владимир не растерялся и здесь, в Сибири. Он сумел собрать и двинуть на Кучума ополчение, состоящее наполовину из татар. Князь Владимир сумел доказать татарам, что их враги — не русские люди, а хан Кучум. И он доказывал это делом. Он брал их на службу толмачами, ямщиками, воинами, оказывал им всяческое доверие, оберегал их права. Таков был наказ Годунова. Татары под властью Москвы должны себя чувствовать не хуже, а лучше, чем под властью Кучума. Кучум — это старый вор!
Едва ли ожидал царь Кучум, что двинутся на него от Тобольска татары. Но вышло именно так. Русско-татарское ополчение отогнало кучумовцев далеко в степи. Кучумовцы были разгромлены на верховьях Ишима. Сам Кучум успел скрыться, бежать. Может быть Мосальский повел бы свое войско еще дальше, в погоню за беглым царем сибирским, но вскоре был отозван князь из Сибири в Москву, получил назначение воеводой в большом полку и выступил против шведов. А на смену Мосальскому явился в 1592 году князь Федор Михайлович Лобанов-Ростовский. Он, как и его предшественники, получил от Годунова подробные инструкции относительно того, что делать. Добрую половину тобольского гарнизона заставил он покинуть стены острога. Одних направил на низовья Оби помогать воеводе Трахониотову строить новый город Березов, который и был поставлен в 1593 году, других в следующем году послал еще дальше — ставить Сургутский острог. А вслед за тем послал из Тобольска человек двести пятьдесят казаков, стрельцов и литвы на юг, в новый город Тару. Так почти все старое население Тобольска рассеялось по стране. Но взамен этим людям прибыли из-за Камня новые — бирючи Годунова продолжали кликать свой клич на всех путях и перепутьях. И город рос.
Князь Федор был человеком опытным в делах восточной политики — недаром провел перед этим несколько лет в Астрахани, русским эмиссаром при так называемом «астраханском царе» Мурате. Этот Мурат был пленным крымским царевичем. Правительство, рассчитывая использовать Мурата в дальнейшем против Крыма, дало пленнику титул астраханского правителя, но князь Федор наблюдал за ним. Там, в Астрахани, Лобанов научился обращению с азиатами. И здесь, в Сибири, эта наука пригодилась.
Дела шли хорошо. Ставили новые остроги, очищали от бродячих орд дороги к стольному городу Тобольску. Помнил сибирский воевода наказ Москвы: так или иначе обезвредить Кучума со всем его родом, налаживать добрососедские отношения с народом Сибири и сопредельных стран Востока, стремиться к тому, чтобы шли в русскую Сибирь охотно торговцы из Бухары, из Джюнгарии, из Кокандского ханства. Тобольск, де, должен стать воротами Востока!
Ворота Азии должны быть величественны. Князь Федор Михайлович чуть ли не заново перестроил весь город. Крепкие, но неказистые постройки из ладийного леса, сооруженные когда-то Данилою Чулковым, показались князю Лобанову недостойными нового времени. Они уж отслуживали свою службу. Пришло время заменить лачужки и землянки добрыми избами. Весь рубленый, новый, нарядный стоял теперь город на Троицком мысе. Если первая церковь представляла собою просто сруб из дерева, покрытый дранью и дерном, из которого торчал крест, так теперь появились церкви с тесовыми крышами, спуски которых были украшены резьбой.
Церкви, высокие башни острога. К этим величественным строениям скоро добавилось еще одно — с крыльями. Специальные мастера, приехавшие из Москвы, соорудили это строение — первую мукомольную мельницу в северной Азии. Ветряная мельница, высокая, точно храм, привлекала особое внимание азиатцев — гостей из степи, лесов и тундры. И все больше в больше таких гостей появлялось в Тобольске, все богаче и богаче делался рынок.