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