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