Шамхал с тарковцами, кумыками и ногайцами встретил русских на реке Койсе, но не удержал переправы и отступил к Таркам. Город Тарки, расположенный амфитеатром по скату скалистой горы близ берега Каспийского моря, не имел особенно сильных укреплений, и взять его не стоило русским большого труда. Но удержаться в нем было трудно. Шамхал был сторонником выжидательного способа ведения войны и следовал дагестанскому правилу «ловить скорпиона за хвост». Воевода начал укреплять Тарки. Но от усиленных работ в жаркие летние дни и от недостатка продовольствия в его войсках начала развиваться лихорадка. Шамхал держал русских в блокаде, сперва широкой, а потом более и более тесной. Встревоженный Дагестан каждый день высылал к нему новые подкрепления, и наибольшую поддержку давал при этом сильный аварский хан, находившийся в родстве с тарковскими шамхалами. Осажденные изнурялись в постоянных битвах и все ждали прибытия грузинской рати, но она не приходила, а что еще важнее – не являлся сват кахетинского царя, которого следовало посадить в Тарках на шамхальство. Храбрый воевода, видя себя в безнадежном и бесцельном положении, решился наконец бросить свое завоевание и отойти обратно на Терек. Но отступление в виду громадных неприятельских скопищ и с большим числом своих больных и раненых, которых нельзя было бросить, требовало чуть ли не большей решимости и отваги, чем наступательное движение в глубину незнакомых гор. Составили совет, на котором недолго спорили, и выступили скрытно ночью, бросив в добычу лукавому «шавкалу» все лишние тяжести. Благодаря азиатской сонливости врагов воеводе удалось уйти на довольно большое расстояние. Но та же темнота осенней ночи, которая оказала покровительство началу похода, явилась предательницей для его продолжения. Проглянувшая в тумане предрассветная луна показала роковую ошибку: отряд сбился с дороги и зашел к болотистому низовью речки Озени. Гребенцы бросились во все стороны и отыскали ногайский кош, из которого привели мальчика-пастуха, не успевшего спрятаться вместе со взрослыми. Пока с его помощью выбирались на чистую дорогу, наступил день. Отступавших стали настигать толпы неприятельской конницы, которая с разных сторон завязывала бой с визгом и криком, а вдали, позади нее, в грозном безмолвии поднимались облака пыли от тяжело двигавшихся главных сил шамхаловой рати. Отбивая наседавшую конницу, русские ускоряли ход и бросали тяжелый наряд и повозки. Бросали и тяжелобольных, и раненых. Тарковцы и аварцы накидывались на них, как голодные волки, и их отчаянные вопли надрывали сердца московских ратников. В полдень надвинулась вся сила басурманская. Нападение вели муллы с поднятыми над головами свитками и с завыванием огненных стихов из Корана. Русские упорно отбивались, то останавливаясь и строясь «в кольцо», то вновь двигаясь и устилая путь каждого перехода телами убитых и раненых, своих и неприятельских. Только на закате солнца русским удалось добраться до Койсу, где наступившая ночь и обоюдное истощение сторон прекратили битву. Воевода Хворостин пережил свое несчастье и привел обратно на Терек едва четвертую часть своего отряда.

«Было ясно, – говорит историк Соловьев, – что Московское государство в конце XVI века еще не могло поддерживать таких отдаленных владений, но тем не менее царь Федор принял тогда же титул «государя земли Иверской, грузинских царей и Кабардинской земли, черкесских и горских князей».

Царь Борис не хотел оставить дело, начатое Федором Иоанновичем, и спустя десять лет, в 1604 году, вновь двинул на Терек сильные полки из Казани и Астрахани с воеводами Бутурлиным и Плещеевым. Опять условлено было с иверским царем, чтобы его грузинская рать выслана была на соединение с русской для совместного действия, и опять грузины не пришли, потому что были взяты шахом на его «кизилбашскую службу». Тем временем русские воеводы с десятитысячным отрядом выступили от устьев Терека и, подвигаясь твердым шагом на Тарки, поставили крепости на Сулаке и Акташе. Отдельные части отряда производили поиски в Эндери, Исти-Су и по другим направлениям, забирая у жителей хлеб, скот и корм для коней. Кумыкская плоскость, казалось, была вся во власти русских, но более воинственное население уходило к шамхалу под Тарки с враждой и злобой за причиненное ему разорение. Тогдашний шамхал, этот митридат для московских воевод, уклонялся от полевых действий и сосредоточивал свои силы в Тарках, оборона которых была приведена им в лучшее положение благодаря указаниям, оставленным Хворостиным.

Прождав бесполезно долгое время подкреплений, обещанных из Грузии, воеводы подошли наконец к шамхаловой столице и, разделившись на две колонны, повели приступ. Старый Бутурлин, славившийся своей доблестью, шел со стрельцами; Плещеев – с боярскими детьми и казаками: донскими, яицкими, терскими и гребенскими. Перед штурмом войска целовали крест и выслушали речь, в которой напоминалось им о костях братьев, здесь полегших, и о русской крови, вопиявшей об отмщении. И стрельцы, и боярские дети, и казаки пошли на приступ с воодушевлением и овладели городом. Городские улицы и площади были устланы неприятельскими телами, а сам шамхал бежал к аварскому хану. Этот шамхал был уже дряхлый старик, почти лишившийся зрения, и потому, удалившись в столь трудную годину от дел, предоставил теперь шамхальствовать и действовать против русских сыну своему Султан-Муту, славившемуся военными способностями.

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

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