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