Уже с конца 1562 года в Москве стали готовить большой поход на Муртазу, который должен был покончить наконец с сибирским ханом. Весной 1563 года в Таре был собран большой отряд из 700 русских стрельцов и 300 ясачных татар, вышедший 9 мая 1563 года вышел в поход на Муртазу.

20 августа 1563 года русские окружили ханскую ставку и начался ожесточённый бой, который шёл весь день и закончился только ночью. Татары потерпели полное поражение и понесли большие потери, включая множество ближайших родственников Муртазы.

В последнем бою в ханской ставке погибла почти вся знать Сибирского ханства. Самого Муртазы и его сыновей: Ахмед Герая и Кучума не было ни среди погибших, ни среди пленных. Как позже стало известно, они в начале битвы вырвались и с немногими целевшими сторонниками убежали в небольшую, но сильную крепость на Ишиме.

Городище занимало мыс коренного берега Ишима высотой 47 метров и со стороны реки оно совершенно неприступно. Крепость защищалась двумя валами и рвами. Первый из них был шириной 12 метров, глубиной в 3,1 метра. После него находился вал, развал которого в ширину был 9,3 метра. Это была высокая стена, примерно в 3,5-4 метра, сооруженная на земляной насыпи из вертикально вкопанных бревен, которые сверху обмазывались глиной. Ров укреплялся рогатками против конницы. Перед рвом шел частокол наклонно вкопанных и затесанных бревен, которые не пропускали всадников непосредственно к стене.

Второй вал отделял в городище небольшой участок и создавал своего рода цитадель. Глубина рва составляла 2,2 метра при ширине в 4 метра. Над ней возвышался развал стены высотой 180 сантиметров и шириной 8,5 метров. Здесь тоже была высокая стена, возведенная на насыпи и укрепленная деревом.

Но даже столь мощные укрепления уже не могли спасти беглого хана. Узнав о приближении русских, он приказал сжечь город, а сам бежал в район озера Зайсан, во владения ойратов, у которых и оставался до самой своей смерти в 1565 г.

После разгрома Муртазы желание принять русское подданство изъявили чатские мурзы, барабинские и теренинские татары. С просьбой о строительстве в его землях русского острога, "чтобы от киргизских людей их оборонить", обратился приехавший в Москву князец эуштинских (томских) татар. В свою очередь он обещал оказать русским представителям содействие в подчинении окрестных племён.

В 1569 г. отряд, состоящий из русских тобольских и тюменских служилых людей, пелымских стрельцов, тобольских татар и кодских остяков поднялся из Сургута по Оби и на р. Томи в 65 верстах от её устья, на высоком мысе на правом берегу у впадения в неё р. Ушайки, поставил Томский острог, ставший важнейшей опорной базой для освоения Средней Оби.

Именно тут русским пришлось столкнуться с сопротивлением своей экспансии со стороны местной народности шорцев, которых русские называли кузнецкими татарами, так как в этом районе имелись богатые месторождения железных руд, а шорцы умели выплавлять железо и изготавливать из него доспехи, котлы и холодное оружие.

В этом краю русские колонисты открыли Салаирский кряж и Кузнецкий Алатау и вышли к западным склонам Абаканского хребта. Таким образом русские в этом крае попали в первую горную страну за Уралом. Достигнув юго-восточной границы Западно-Сибирской равнины.

Тогда же русским пришлось столкнуться с новым врагом — т. н. "енисейскими киргизами", которые были достаточно сильным и воинственным народом. И хотя собственно киргизов в середине XVI века было не так уж и много, всего около полутора тысяч человек, но они держали в подчинении гораздо более многочисленные народы. При этом киргизские князья находились в вассальной зависимости от могущественного монгольского государства Алтын-хана и платили ему дань.

Западная граница киргизских владений проходила по реке Кие, притоке Чулыма, восточная — по Енисею. Северной границей их владений была река Кемчуг, которая тоже впадает в Чулым в том месте, где она делает довольно резкий поворот на запад, к Оби. Южнее киргизов, южнее реки Уйбат, кочевали маты, которые затем откочевали за Саяны, во владения Алтын-хана.

Киргизское войско, несмотря на малочисленность, представляло собой очень серьёзную военную силу. Воины имели отличное оружие и доспехи. Киргизы использовали панцири двух типов из металлических пластин, кожаные доспехи из толстой кожи и кожаные боевые рубахи. Один тип панциря состоял из 16 квадратных пластин с двумя или четырьмя рядами бортиков, которые крепились к кожаной основе заклепками. Второй тип панциря состоял из 20 прямоугольных пластин, нашитых на кожаную основу. Использовались киргизами и кольчуги, а голову воина защищал сфероконический шлем, с забралом, козырьком и кольчужной бармицей.

В 1571 г. киргизы прошли походом и разорили несколько ясачных волостей по Чулыму. Русские ответили несколькими рейдами по киргизским землям.

В 1572 г. несколько томских казаков посылались к "кузнецким татарам" для выяснения возможности сбора там ясака. Разведчики вернулись с самыми неутешительными известиями: "Живут в крепостях великих, и болота обошли и зыбели великие и ржавцы; а зимой живут снеги великие, и воевать их, кроме лета, из жары, невозможно".

Неудача в Кузнецкой волости не остановила русских в попытках расширить ясачные волости. В 1573-1574 годах они предприняли настоящее наступление на владения киргизов. В 1573 году казакам удалось все-таки наложить ясак на несколько татарских родов, живших по Чулыму. Томские служилые добрались по Чулыму и Кемчугу, через горы Восточного Саяна до матов, моторцев, тубинцев, живших на Енисее и бывших в зависимости от киргизов и Алтын-хана.

В марте 1574 г. русские заключили союз с телеутским князем Конаем. Договор оказался взаимовыгодным. По нему русские отказывались от взимания ясака с телеутов, но в обмен требовали предоставление вооружённой силы для поддержки малочисленных русских отрядов (подобное практиковалось и в реальной истории). В свою очередь телеуты, вынужденные воевать с Алтын-ханом, ойратами и казахами, получали право на получение помощи с русской стороны.

И очень скоро этому союзу пришлось пройти испытание на прочность. В начале 1574 года киргизы подготовили общее выступление вместе с чулымскими татарами против русских. В тот год состоялся большой поход на русские волости и Томск. 8 июля 1574 года Томск подвергся нападению, а вся подгородная волость — разгрому. Киргизы осадили город и перебили в подгородных селах много служилых казаков, стрельцов и пашенных крестьян. После чего, разорив и разграбив весь Томский уезд, киргизы ушли, а русские стали готовить ответный поход.

Зимой 1574-1575 гг. отряд из 40 казаков отправился к "кузнецким татарам", но вынужден был возратиться, не добившись успеха. Летом 1575 г. казаки основали близ устья р. Кондомы Абинский городок (ныне г. Абагур). А в конце 1575 года в Кузнецкую волость отправился большой отряд служилых людей, около 200 человек.

Этот поход был настоящим завоеванием Кузнецкой волости. Русский отряд, разделившись на несколько групп, поднялся в долины рек Мрас-Су и Кондомы. Казаки захватили несколько улусов, взяли там заложников и силой стали собирать ясак. Кузнецкие татары, оказавшись неспособными отразить нападение, обратились за помощью к киргизам и ойратам. В Кузнецкую волость пришло большое войско, общей численностью до пяти тысяч человек.

Русские были окружены и осаждены в укрепленном городке, где просидели в осаде два с половиной месяца, после чего им удалось с боем прорвать окружение и вырваться в Томск.

Но неудача похода не обескуражила томского воеводу. На следующий год, в августе 1576 года, он снова отправил большой отряд в Кузнецкую волость. Киргизы вновь пришли в Кузнецкую землю с войском. Но на этот раз русские учли свои предыдущие ошибки, и столкновение закончилось разгромом объединённых сил енисейских киргизов и чулымских татар. После этого кузнецкие татары стали платить дань русским.

Русские воспользовались благоприятной ситуацией. Томские служилые прошли походом по землям чулымских татар. В 1577 году русский отряд дошел до Енисея и обложил данью тубинцев и маторцев. А для укрепления русской власти в долине Томи в мае 1577 г. в устье Кондомы на земле "кузнецких татар" был основан Кузнецкий острог (теперь г. Новокузнецк), что значительно укрепило положение новых властей в Горной Шории. В то же время в бассейне р. Чулым, правого притока Оби, были поставлены небольшие острожки — Мелесский и Ачинский, чьи гарнизоны должны были оберегать местных жителей от вторжения киргизских князьков и монгольских ханов.

Зимой 1578 г. из Тобольска на Енисей был отправлен отряд тобольских служилых людей, которые у волока на Енисей поставили Маковский острожек. Но одного укреплённого пункта оказалось недостаточно для обеспечения перехода по волоку, и осенью того же года — зимой 1579 г. — выше устья Кеми на левом берегу Енисея русские поставили острог Енисейск, из которого можно было не только держать в подчинении и оборонять уже объясаченные волости по Енисею, но и продолжить расширение русских владений, а также контролировать устье Ангары, откуда приходили тунгусы (эвенки) и буряты.

Правда, тунгусские князцы оказали сопротивление служилым людям при постройке этих острогов. Однако русские сумели за два года объясачить тунгусов, проживавших на Нижней Ангаре и по её левому притоку Тасеевой. Но окончательное поражение "немирным" тунгусам нанесли только в 1588 г. в бою на Ангаре в устье р. Рыбной, после чего жители этого района окончательно присоединились к Русскому государству.

После принятия в подданство тунгусов, живущих в устье Ангары, русские владения стали охватывать владения киргизов и их данников с двух сторон: с запада и с севера. Татарские волости по Чулыму и Кие, платившие дань киргизам, стали клином киргизских земель, которые выступали в сторону русских владений. Но, с другой стороны, русские вторглись во владения, которые были подвластны киргизам по Енисею. Их владения доходили до устья Ангары, и потому русские, поставив Енисейский острог, уже распространили свое влияние на самые северные владения киргизских князей.

В 1580 году томский воевода попытался подчинить эти территории путём постановки русского острога в верхнем течении Чулыма, который отрезал бы их от киргизов. Но от этой идеи отказались, как слишком рискованной. В таком случае русский острог был бы окружен враждебным населением, и помочь ему в случае необходимости было бы невозможно. Потому было принято несколько другое решение — укрепить русско-киргизскую границу на дороге от Томска до Енисейска, которая как раз проходила вблизи самых северных кыргызских владений.

Летом 1581 года отряд из Томска поставил острог в устье Кемчуга при впадении его в Чулым, в центре Мелесской волости, отчего сам острог стал назваться Мелесским. Это был русский форпост среди многочисленного татарского местного населения.

В результате этих завоеваний русские владения в Сибири к началу 80-х годов XVI века распространились на 1800 километров к востоку от Тобольска. Южная граница сибирских владении представляла собой практически прямую линию, протягивающуюся от Тюмени и Тобольска через Тару и Томск до Енисейска, который был некоторое время самым восточным городом Русского государства, чьи владения в Западной Сибири в то время представляли собой громадный клин, протянувшийся почти на две тысячи километров от Урала до устья Ангары, впадающей в Енисей. Приенисейские владения были вершиной этого клина.

Но восточное направление было не единственным, куда в это же самое время шло русское проникновение. Присоединение Астрахани открыло Русскому государству путь на юг, в сторону Кавказских гор. Уже в ноябре 1552 г., вскоре после разгрома турецкой армии в низовьях Волги, "приехали к государю царю и великому князю черкасские государи князи Маашук князь да князь Иван Езболуков, да Танашук князь бити челом, чтобы их государь пожаловал, вступился за них, а их з землями взял к собе в холопи, а от Крымского царя оборонил". А в июле 1554 г. в Москву приехал посол от кабардинских князей, который "пришел от братии, от Кабартынских князей черкаских, от Темрюка да от Тазрюта князя бити челом, чтобы их государь пожаловал, велел им собе служити и в холопстве их учинить, а на Шавкал был им государь пожаловал, астраханьским воеводам велел помочь учинити. Да говорил Кавклыч-мурза Черкаской: только их государь пожалует, учинит у себя в холопстве и помочь им учинит на недругов так же, как их братью пожаловал, черкаскых жаженьских князей Машука и Себока з братьею с их, и с кабартинскими черкасы в одной правде и заговоре иверский князь и вся земля Иверская и государю с ними бьют челом, чтобы государь царь и великий князь их по тому же пожаловал как и тех всех".

Установление связей с адыгами Северного Кавказа создавало для России весьма выгодную стратегическую позицию в войне против Крымского ханства, которое таким образом было вынуждено действовать одновременно на нескольких направлениях, распыляя силы. Активные совместные действия русских и западных адыгов против крымцев продолжались несколько лет, однако задуманный русским правительством "большой поход" против Крыма так и не состоялся, по уже ранее описанным причинам. А отвлечение внимания Русского государства на свои северо-западные рубежи привело к потерям им своих позиций в Западной Черкессии. Однако уход русских из этого региона нельзя было назвать полным. Кабардинский князь Темрюк Идарович не только не стал рвать союз с Иваном IV, но и всячески пытался укрепить свои связи с ним, рассчитывая на его поддержку в своём противостоянии как крымцам, кумыкам, так и другим кабардинским князьям. И его расчет оказался верен. Не желая терять свой форпост на Кавказе (тем более, что через Кабарду была установлена связь с восточно-грузинскими государствами), Россия оказывала всевозможную поддержку Темрюку, вплоть до присылки воинских контингентов, с целью силового воздействия на его противников. Дело доходило до того, что в 1557 г. из России были присланы в Кабарду "попы крестианские" — "по их обещанию и челобитью крестить их, кабартанских черкас" (в то время ислам только начал проникать в черкесские племена, среди которых ещё были сильны позиции христианства и пережитки языческих верований).

В ответ, ко двору Ивана IV выезжали для службы — одни временно, иные навсегда — и другие кабардинские князья. Кабардинские конные отряды включались в состав русских войск, действовавших в Ливонии, обычно в передовой полк.

Вслед за тем имело место окончательное оформление отношений службы и подданства кабардинцев. В конце 1556 г. царь Иван IV послал к Темрюку "и ко княине его и к детям их и к племяни их свое великое жалование", "платье и деньги и купки и ковши и иные суды серебряные", и Темрюк "со всею своею братьею и з землею учинился государю в службе". Таким образом, во внешних сношениях Темрюк, с 1557 г. принял в противовес крымско-турецкому нажиму ярко выраженную пророссийскую ориентацию.