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