Русские силы насчитывали 13 тыс. человек детей боярских, их людей, казаков и стрельцов. 22 июня на марше Шереметев получил известие, что значительные силы крымского хана в это время двигаются в глубь Русского государства другой дорогом, причем крымчаки о русском походе ничего не знают. Отправив нарочного в Москву и отделив часть войск,Шереметев с оставшимся отрядом двинулся наперехват крымчакам. За Сосной, на расстоянии полутора верст от Тулы, Шереметев встретился силами крымского хана, который шел назад, в Крым, узнав о движении русских войск. 3—4 июля произошло двухдневное сражение на Судьбищах, котором русские противостояли превосходящим татарским силам.
Осенью 1556 года одновременно с нападением действовавшего на стороне Ивана Грозного князя Вишневецкого на крымскую крепость Ислам-Кермен пятигорские черкесы князья Таздруй и Сибок взяли турецкие города Темрюк и Тамань, использовав при осаде пушки, полученные от московского царя. Однако долго удержаться на Таманском полуострове им не удалось, и в 1557 году многие черкесские князья во главе с Сибоком и Машуком покинули родину и бежали в Москву. Там Сибок и Машук крестились и получили от царя соответствующую службу. Перебрался в Москву и шурин Девлет-Гирея Татар-мурза, причем долго черкесы в столице не пробыли: вскоре черкесские отряды были переправлены в Ливонию, где вместе с русскими участвовали в войне. Командование старалось направлять черкесов только на передний край.
После взятия русскими Астрахани московского подданства запросил и кабардинский князь Темрюк Айдарович (Идаров), силы которого оказались как нельзя более кстати для помощи сражавшемуся против Крыма Вишневецкому. В 1558 году посол князя Гемрюка Кавклыч был отправлен к своему патрону с предложением собрать войско и двигаться на помощь Вишневецкому мимо Азова. Осенью 1559 годак Вишневецкому на Дон прибыл мурза Ичурук, которого Вишневецкий взял с собой в Москву. Представляя западных адыгов, мурза «бил челом» царю, «что - бы их государь пожаловал, дал бы воеводу своего в Черкесы и велел бы их всех крестити». Ичурук понимал, что в условиях турецко-русского противостояния религия играет вполне определенную роль. Православная церковь сохранила среди черкесов влияние с византийских времен и теперь связывалась в сознании с сильным Русским государством, ислам же — с Крымом и османами. В 1560 году были отпущены из Москвы князья Сибок и Машук, вернувшиеся с Ливонской войны. Вместе в ними отправился на Северный Кавказ и князь Вишневецкий со своими людьми. И черкесы, набравшиеся военного опыта, и Вишневецкий получили от царя приказ воевать против крымского хана, чем и занялись с известным успехом и к большому неудовольствию как Стамбула, так и европейских дворов, видевших в крымских татарах сдерживающий фактор русской экспансии.
Позднее позиции Москвы в Западной Черкессии значительно ослабли. Сначала Сигизмунд Август смог переманить к себе Дмитрия Вишневецкого, не поладившего с Иваном Грозным, потом и черкесы охладели к союзу с русскими. Более того, некоторые черкесские князья со своими дружинами приняли приглашение польского короля и поступили на службу в Великое княжество Литовское.
Со второй половины 50-х годов XVI века интенсивными становятся кабардино-русские связи. Этому способствовала женитьба Ивана IV в 1561 году на дочери Темрюка Идарова, получившей в Москве после крещения имя Мария, причем царь не скрывал, что придает этому факту политическое значение. До того он засылал посольства с предложением своей руки в Польшу и Швецию, однако получил отказ. Присоединение Кабарды позволило бы нейтрализовать крымского хана и избавить государство от бесконечных войн на юге. Однако признание кабардинцев подданными русского царя и их служба государству не означали включения Кабарды в государственные границы и не вели к назначению туда русской администрации. Раздробленность Кабарды на отдельные уделы приводила к тому, что далеко не всегда и не все кабардинские князья полагали себя вассалами московского царя. Однако первое кабардинское посольство с просьбой принять в свои пределы явилось в Москву в 1557 году, причем представляли кабардинцы не только несколько своих родов (Идаровичей и Таусалтановых), но и союзных себе кахетинцев.
В 1558 году организовавший посольство князь Темрюк прислал в Москву своих сыновей Булгерука и Салнука ( Салтанкула) с просьбой предоставить им Убежище. Салнук был крещен, получив имя Михаил, научился грамоте и, оставшись при дворе Ивана Грозного, стал впоследствии одним из видных опричников. Побывали при дворе царя и другие сыновья Темрюка, а на его дочери царь женился. От этого брака был сын Василий, рано умерший.
Официально переход кабардинцев под покровительство русского царя состоялся в 1561 году, когда из Москвы к Темрюку было отправлено с богатыми дарами посольство и Темрюк признал свой переход на русскую службу. Иван Грозный, женившись на Марии Темрюковне, обрел массу родственных связей и за пределами Кабарды. Одна из сестер его жены — Алтынчач была замужем за астраханским царевичем Бекбулатом, братом царевича Тохтамыша перебравшегося на службу в Москву в 1556 году. В 1561 году сам Бекбулат вместе с сыном Саид-Булатом, впоследствии ставшим известным как Симеон Бекбулатович, тоже выехал служить в Москву, где давно стремились пригласить его, рассчитывая собрать при дворе основных претендентов на астраханский трон. Другая сестра Марии — Малху-руб — была женой сына ногайского князя Измаила Тинехмата. К нему Иван IV прислал своего посла М. Т. Петрова с твердой инструкцией напомнить ногайскому князю о его родстве с русским царем и заручиться миром. Справедливости ради следует признать, что и после этого Тинехмат, в отличие от своего отца, предпочел придерживаться прокрымской ориентации.
Сам Темрюк Айдарович был большим, или начальным, князем в Кабарде, где ему приходилось то и дело прибегать к вооруженной силе во взаимоотношениях с другими кабардинскими князьями. Враждуя с шамхалом, он имел союзнические отношения с Грузией и вел ярко выраженную прорусскую политику. Москва неоднократно помогала Темрюку в его междоусобицах и против внешних врагов. С 1558 по 1567 год у него шесть раз побывали русские послы и, по крайней мере, четыре раза ему была оказана сильная и длительная военная помощь, причем особенно эффективны были отряды стрельцов, вооруженных огнестрельным оружием. Кроме того, по просьбе Темрюка и для защиты е земель русские построили крепость на Тереке, ставшуюпричиной дипломатической войны, подкрепленной также настоящими боевыми действиями крымчаков против Москвы.
В 1562 году царь отправил в Кабарду войска во главе с воеводой Плетеевым, а в 1565 году экспедиционный корпус возглавляли воеводы Дашков Ржевский. Однако это не остановило крымских набегов, а весной 1570 года хан Девлет-Гирей напал на Темрюка. В бою при Ахупсе (левый приток Кубани) Темрюк был смертельно ранен, а два его сына попали в плен. Девлет-Гирей на следующий год предпринял удачный для него рейд на русские земли и 24 мая 1571 года сжег Москву. России пришлось покинуть тогда свой город на Тереке, его отстроили позднее.
Дальнейшие события, а именно победа в конце июля 1572 года русских войск под командованием Михаила Ивановича Воротынского над крымским ханом, вернули Русскому государству пошатнувшийся престиж, и весной 1578 года в Москву прибыло новое кабардинское посольство с подтверждением подданства, а также с просьбой восстановить крепость на Сунже и прислать войска для защиты от крымских татар. Во главе этого посольства в русскую столицу прибыли брат погибшего Темрюка, старший князь Камбулат Идаров, а также сын Пшеап-шоки Кайтукина Казый и Созоруко Тапсаруков из рода Таусултановых, являвшиеся представителями наиболее влиятельных в Кабарде княжеских фамилий. Вместе с Камбулатом Идаровым приехал его сын Хорошай, получивший при крещении имя Борис и впоследствии ставший в России крупным военачальником. В Москве Камудат получил от царя грамоту с признанием его старшинства в Кабарде, а на Терек был послан сильный отряд стрельцов под командованием Луки Новосильцева, восстановивший крепость у устья Сунжи. В 1589 году, после смерти Камбулата Идарова и избрания новым старшим князем Янсоха Кайтукина, подданство Кабарды в Москве было еще раз официально подтверждено.
Находились в подданстве у русского царя и западные черкесы (адыги), о чем свидетельствуют дипломатические документы 1600 года, а в 1614—1615 годы западные черкесы присягали на верность царю Михаилу Федоровичу. Как и в ряде других случаев, русское правительство ограничилось формальным признанием своего главенствующего положения, не прислало к западным черкесам русской администрации и не обложило их податями. В 1634 году в Терки, где находился центр русского управления краем прибыли с подтверждением подданства князья Безрука Камурзин от темиргоевцев и Мурза Отлепшукин Левов от абазин. Позднее, когда в Терках проходили переговоры о присоединении к России Казиевой Кабарды, в переговорах участвовали и абазинские мурзы в качестве одной из заинтересованных сторон. Считается, что абазины окончательно присягнули русскому царю вместе со своими князьями в 1645 году.
Захват русскими Астраханского ханства и демонстрация, таким образом, их военного превосходства немедленно повлек за собой многочисленные визиты в Москву послов от шамхала, из Дербента и других мест Дагестана. В 1555 году ко двору Ивана Грозного явились дагестанские послы с предложением дани и с просьбой принять на службу. Разумеется, отказано им не было. Одной из причин спешного перехода дагестанских владетелей в царское подданство являлось перекрытие русской администрацией традиционных торговых путей из Дербента через Астрахань. Теперь, чтобы отправлять и получать товары, требовалось разрешение Москвы, а получить его проще всего было через русское подданство.