Казаки и соседние с ними кавказские народы страдали от жестоких набегов крымских ханов. Особенно тяжело приходилось жителям Западного Кавказа и Кабарды. Крымчане уводили тысячи жителей в плен и продавали их в неволю. Особенно ценились за свою красоту черкесские женщины, которых отправляли в Турцию. Там некоторые из них попадали в султанский гарем и добивались большого влияния, но участью остальных было самое настоящее рабство. Набеги работорговцев были настоящей напастью для черкесских племен, которые постоянно искали союзников для защиты от врага. Первыми за помощью к московскому царю обратились кабардинские князья. Буквально через месяц после победы русских над Казанским ханством в Москву прибыли «черкесские» (так называли в XVI веке предков нынешних адыгейцев, кабардинцев и черкесов) князья с просьбой, чтобы русский царь «вступился за них и от крымского хана оборонил».
Взятие Астрахани повлекло за собой присоединение к России Большой Ногайской Орды. Ее князь Исмаил еще в 1552 году бил челом Ивану Грозному с просьбой о русском подданстве и защите от крымцев. В 1557 году в Москву явились дагестанские послы с просьбой о принятии «под руку» русского государя и защите от врагов «со всех сторон». В том же году прибыли послы от последних никому не подвластных кабардинских князей — Темрюка и Тазрюта (Тазурта) с челобитьем о подданстве и «бережении от врагов». Приняли русское подданство также абазины, жившие у Черного моря. С этого времени русские и кавказские народы начали предпринимать совместные военные походы против общих врагов. Так, в 1558 году «черкесы пятигорские многие» участвовали в походе русских в Ливонию, русские с большими силами черкесов и ногаями «ходили промышляти» над крымским ханом.
В 1561 году, после смерти первой жены Анастасии Романовой, Иван IV женился на кабардинской княжне Марии (Кученей) Темрюковне, дочери князя Темрюка Айдаровича. Вскоре князь попросил у зятя помощи в борьбе с крымскими татарами, участившими набеги на Кабарду. Московский царь послал на Терек воеводу князя Андрея Бабичева и келаря Петра Протасьева с большим войском. В 1567 году на левом берегу Терека, против устья Сунжи, была заложена крепость, получившая название Терской. Ее гарнизон состоял частично из государевых ратных людей, частично из гребенских казаков. Крепость эта была поставлена на главном торговом пути из Крыма к Каспийскому морю. Турецкий султан и крымский хан совместно потребовали от русского царя срыть ее. Требование это совпало со страшным разорением Москвы крымскими татарами в 1571 году, а также с затруднениями в ходе Ливонской войны. Иван IV был вынужден объявить султану о разрушении Терской крепости и отводе войск в Астрахань.
Царь выполнил свое обещание, но не до конца. Крепость снесена не была, из нее только вывели «государевых людей» — стрельцов. Их заменили, как вскоре сообщили султану соглядатаи, некие «воровские люди» — казаки, которые живут сами по себе и никого не слушают. Очевидно, весть о связях казаков с Москвой еще не достигла Стамбула, что было весьма удобно для царя. В 1578 году воевода Новосильцев вернулся в Терскую крепость и «на реке на Тереке на устье Сунжи реки город поставил». Следом пришли вольные волжские казаки и построили в устье Терека укрепленный городок, названный Трехстенным. Крымско-каспийский торговый путь оказался полностью под русским контролем.
Вскоре к Руси в поисках защиты от персидского шаха и турецкого султана обратился грузинский царь Александр. В 1584 году в Москву к царю Федору Ивановичу прибыло грузинское посольство, заявившее: «Сам своею головою и со всею своею землею под кров царствия и под вашу царскую руку рад поддается, понеже государь наш и земля наша Христьянская, а от неверных турок в велицей беде и в утеснении, и в том твоя царская воля, как государя нашего и его землю пожалуешь от таких и неверных богомерзких агарян оборонити». Для переговоров на Кавказ было направлено посольство — воевода Михаил Бурцев и келарь Протасьев с ратными людьми.
Но, чтобы реально помочь Грузии, необходимо было открыть дорогу с Северного Кавказа в Закавказье. Самым удобным был путь через каспийское побережье. Для этого в 1589 году было решено поставить в устье Терека, на его притоке Тюменке новую крепость. Город был назван Терским или Терками, а старая Терская крепость в устье Сунжи с тех пор стала именоваться Сунженским городищем. Гарнизон Терской крепости состоял из трех стрелецких полков. Кроме того, сюда пришла и расселилась вокруг часть гребенских и немало яицких казаков, которые стали родоначальниками терского казачества.
За год до основания Терской крепости, в 1566 году, в Грузию было отправлено первое русское посольство. Послы отметили, что при движении по реке Сунже к Дарьяльскому ущелью располагаются чеченские «землицы», известные под названиями «окохи», «шибуты» и «мичкизы». Между чеченцами и гребенскими казаками сложились вполне мирные отношения, скреплявшиеся куначеством. Тесные связи существовали между казаками станицы Червленной и чеченцами из селения Гуни, переселившимися сюда из Нахч-Мохка. Они ходили в гости и при необходимости оказывали друг другу помощь против врагов. Гребенские казаки многое позаимствовали у чеченцев по части быта и домашнего обихода: национальный костюм, танцы, музыкальные инструменты, игры, скачки и состязания в джигитовке. В свою очередь равнинные чеченцы переняли у русских некоторые приемы строительства домов, обработки земли и разведения огородов.
В конце XVI века чеченским «землицам» и феодальным владениям отводилось особое место во взаимоотношениях с Россией. Прежде всего это были экономические отношения: излишки продуктов своего производства (земледелия, скотоводства, домашних промыслов) чеченцам было выгодно обменивать в соседних казачьих городках. Большим спросом у самих чеченцев пользовались изделия русских мастеров — ткани, меха, оружие. Не менее важным был и политический аспект. В эти годы значительно усилилось военное давление на Кавказ Персии, Турции и Крымского ханства. В 1578 году в Закавказье вторглось 200-тысячное войско турецкого султана под командованием Мустафы Лала-паши. В том же году в северокавказские пределы вторгся крымский калга (главнокомандующий) Адиль-Гирей, выступивший против Персии. Татарская орда была разбита персами, а осколки ее, отступавшие в Крым и грабившие по дороге все подряд, были разгромлены русским воеводой на Тереке.
Противодействие интересов Персии, Турции и Крымского ханства с Россией в Кавказском регионе со временем только обострялось. Грузия, находившаяся в наиболее уязвимом положении, все чаще обращалась к России за помощью. Самый удобный путь сообщения с Закавказьем — Дарьяльский проход — пролегал через земли чеченцев и ингушей, без помощи которых наладить такое сообщение было очень трудно.
Одними из первых союзников России на Кавказе стали окоцкие (чеченские) мурзы Ушаром и его сын Ших, родовые земли которых располагались в верхнем междуречье Аксая и Акташа. Князь Ушаром со своим улусом и войском не раз помогал послам русского царя совершать непростые путешествия в Грузию и поддерживал добрые отношения с казачьими городками на Тереке. Эти отношения он завещал продолжать и своему сыну Шиху. Исполняя завещание отца, Ших-мурза первым из окоцких владетелей пришел служить в новый Терский городок на реке Тюменке. По грузинским и русским источникам войско Ших-мурзы составляло немалую силу — пятьсот конных и пятьсот пеших воинов. Следом за ним стали являться в Терки и другие горские владетели.
Царь Федор Иванович называет Ших-мурзу в своих царских грамотах князем, а подвластным ему селениям дает имена «Шихов юрт», «Шихов улус», «Шиховы кабаки» (то есть поселения). Под контролем мурзы находились наиболее удобные пути в Грузию, которыми чаще всего пользовались русские послы. Ших-мурза, видимо, имел большое влияние на чеченских владетелей, чьи земли находились в районах левобережья Аргуна и верховьях реки Чанты-Аргун. Так, при посредничестве Ших-мурзы Окоцкого и его поручительстве владетели «землиц» Чачана и Тарлоя обязались помогать людям русского царя и охранять их на пути в Грузию.