В ту же весну, что было отправлено посольство в Москву, пришел к Ермаку мурза Сеинбахта Тагин и поведал, что царевич Маметкул стоит на реке Вагае в 100 верстах от Искера. Атаманы отобрали 60 проворных молодцов и послали на Вагай. Ночью казаки напали на татар, многих побили, а Маметкула «взяли жива» и привели в город. Ермак принял царевича как дорогого гостя, но держал под крепкой стражей, а в 1584 г. отослал в Москву. Фёдор Иоаннович пожаловал Маметкула жалованьем и вотчиной. Уже в 1585 г. Маметкула ввели в командный состав одного из московских полков, а в следующем году он возглавил сторожевой полк.
Между тем атаманы совершали походы по Иртышу и Оби и на запад — на Тавду, подчиняя остяцких и вогульских князцов. Обычно сопротивление было слабое. Казаки покоряли не столько оружием, сколько своей славой. На стругах играла музыка, на берег казаки сходили в красивых кафтанах. Все склонялись. Станичники не только собирали ясак, но любопытствовали местным богам, слушали предсказания шаманов и искали золотую бабу, знаменитого идола угров. Но золотую богиню найти не удалось. Бывали и серьезные бои, в одном из них погиб Никита Пан. В подобных случаях казаки поступали жестоко.
Богдан Брязга, посланный вниз по Иртышу собирать ясак, встретил в устье Аремзянки татар весьма упорных, засевших в городке с крепким палисадником и не желавших ни о какой сдаче слушать. Брязга пошел на приступ: «Городок крепкий взял боем и многих лутчих мергеней[170] повесил за ногу и растрелял... и ясак собрал за саблею и положил на стол кровавую, и велел верно целовати за государя царя». Казаки запомнили эту историю не из-за казни заводил — обычного дела в те времена — или целования сабли, принятого при присяге у местных татар, а из-за унизительности казни и присяги. Ермак никогда себе такого не позволял. Но на первых порах жестокость Брязги работала: «Татары и за страх грозы не смели не токмо руки поднять, ниже слова молвити во всей волости Кадцынской».
Для врага Ермака, Кучума, в ту пору все складывалось плохо. В сибирских степях появился претендент на трон и к тому же кровник. Из Бухары с отрядом казахов пришел князь Сейдяк (Сеид-хан) — сын и племянник казнённых Кучумом братьев-тайбугидов — Бекбулата и правителя Сибири Едигера. Многие татары тогда откачнулись к Сейдяку как к законному владыке Сибири. Начался раскол и в лагере Кучума. От него отделился влиятельный вельможа — Карача, со своими людьми он откочевал к Чулымскому озеру. Но Кучум не сдавался, хоть войско его сильно уменьшилось. Он жестоко карал отшатнувшихся от него татар и внимательно следил за казаками, выжидая момент для удара.
Удар по ермаковцам нанес не Кучум, а Карача. В сентябре 1584 г. он прислал к Ермаку послов с подарками и обещанием дать шерть российскому государю, если казаки помогут ему в походе против ногайцев. Ермаковцы посовещались и решили отрядить Караче в помощь Ивана Кольцо с 40 казаками. Казаки прибыли в стан Карачи, их радушно приняли, устроили пир и... всех зарезали. Ермак со станичниками очень переживали гибель товарищей, но сыскать Карачу в обширных Барабинских степях было что иголку в сене.
В ноябре 1584 г. в Кашлык пришла долгожданная помощь — 300 стрельцов во главе с князем Семёном Волховским и стрелецким головой Иваном Глуховым. Казаки на радостях щедро одарили пришедших соболями и лисами. Вскоре, однако, выяснилось, что стрельцы не привезли с собой никаких припасов. Путь ермаковцев оказался им не по плечу: стрельцы затратили на него пять месяцев. Перетаскивая струги через волок, обессилели и бросили их вместе с припасами; шли налегке, надеясь на Ермака. Воеводы плохо представляли жизнь в Сибири: не знали, что хлебопашество у сибирских татар мало развито и казаки, обеспечив себя зерном в обрез, сами надеялись на хлеб из России. Казаки помогли чем могли: устроили стрельцам зимние жилища, снабдили мехами, чтоб не замерзли, но продуктов много они дать не могли. Как назло, зима оказалась на редкость холодной — охотиться и ловить рыбу не было возможности. Начался голод, к нему присоединились болезни. К концу зимы умерло большинство стрельцов, вместе с воеводой Волховским, и немало казаков. Выжившие — 200 казаков и 50 стрельцов с воеводой Глуховым — были больны и слабы.