Утверждение в устьях Волги открыло Московскому государству целый мир мелких владений в Прикавказье: князья их ссорились друг с другом, терпели от крымцев и потому, как скоро увидали у себя в соседстве могущественное государство, бросились к нему с просьбами о союзе, свободной торговле в Астрахани, некоторые - с предложением подданства и таким образом незаметно, волею-неволею затягивали Московское государство все далее и далее на восток, к Кавказу и за него. Тотчас после падения Казани, в ноябре 1552 года, приехали в Москву двое черкасских князей с просьбою, чтоб государь вступился за них и взял их себе в холопи. В августе 1555 года приехали в Москву князья черкасские жаженские Сибок с братом Ацымгуком да Тутарык, в сопровождении 150 человек. Били они челом от всей земли Черкасской, чтоб государь дал им помощь на турецкого и крымского царей, а они холопи царя и великого князя с женами и детьми вовеки. Государь пожаловал их своим великим жалованьем, насчет же турецкого царя велел им отмолвить, что турский султан в миру с царем и великим князем,Шуйск а от крымского государя хочет их беречь, как только можно. Князь Сибок просил, чтоб государь велел окрестить сына его, а Тутарык просил, чтоб окрестили его самого. Летом 1557 года приезжали в Москву другие черкасские князья. Тогда же двое князей черкасских кабардинских, Темрюк и Тизрют, прислали бить челом, чтоб государь велел им себе служить и велел бы астраханским воеводам дать им помощь на шамхала Тарковского; посол говорил: только государь их пожалует, как пожаловал жаженских князей, и поможет на недругов, то князь грузинский и вся земля Грузинская будут также бить челом государю в службу, потому что грузинский князь в союзе с кабардинскими князьями. С другой стороны, из владений шамхала и князя тюменского (с берегов Терека) пришли послы с челобитьем, чтоб государь велел им быть в своем имени, приказал бы астраханским воеводам беречь их со всех сторон, а торговым людям дал бы дорогу чистую: что государь велит себе прислать, то будут присылать каждый год. Черкасские князья просили помощи на шамхала, шамхал просил помощи на черкасских князей; тюменский мурза просил помощи на дядю своего, тюменского князя: посадил бы государь его на Тюмене, а он холоп государев; подданные шамхала просили, чтоб государь дал им другого владетеля, а они всею землею холопи государевы; ханы хивинский и бухарский присылали с великим челобитьем, чтоб государь дал дорогу купцам их в Астрахань.
Легко понять, как смотрели на все это в Крыму. Попытка отвлечь Иоанна от Казани нападением на московские украйны не удалась; деятельно помогать Казани и Астрахани, сильными полками вести оборонительную войну без надежды на грабеж не нравилось разбойникам: они умели только раздувать восстания на Волге и не умели их поддерживать, вследствие чего Казань и Астрахань стали московскими городами. По возвращении Иоанна из-под Казани Девлет-Гирей завел опять пересылку с Москвою, осенью 1553 года прислал даже шертную грамоту, написанную точно так, как требовал царь, только без царского титула; прописано было даже, что если московский посол потерпит бесчестие в Крыму, то государь московский имеет право подвергнуть такому же бесчестию крымского посла у себя. По-прежнему хан жаловался, что Иоанн присылает ему мало поминков, а если пришлет больше, то он и помирится крепче. Иоанн велел отвечать, что дружбы подарками не покупает, и, чтоб мир с ханом был крепче, велел строить город Дедилов в степи против Тулы. Летом 1555 года, поднявши Дербыш-Алея в Астрахани против русских, Девлет-Гирей вздумал опять попытаться напасть врасплох на московские украйны. По обычаю - в одну сторону лук натянуть, а в другую стрелять - хан распустил слух, что идет на Черкасов. Обязавшись защищать этих новых подданных, Иоанн первый из московских государей решился предпринять наступательное движение на Крым и отправил боярина Ивана Васильевича Шереметева с 13000 войска к Перекопи в Мамаевы луга промыслить там над стадами крымскими и отвлечь хана от черкас. Шереметев двинулся, но на дороге получил весть, что хан вместо черкас идет с 60000 войска к рязанским или тульским украйнам. Шереметев дал знать об этом в Москву, и царь, отправив тотчас же воевод, князя Ивана Федоровича Мстиславского с товарищами, в поход, сам выступил за ними на третий день с князем Владимиром Андреевичем в Коломну. Здесь дали ему знать, что хан идет к Туле; Иоанн двинулся туда же; хан, узнавши, что сам царь идет к нему навстречу, поворотил назад. Между тем Шереметев шел за ханом с намерением хватать малочисленные татарские отряды, когда они рассеятся для грабежа по украйне, и прежде всего отправил треть своего войска на крымский обоз, который с половиною лошадей татары обыкновенно оставляли назади, в расстоянии пяти или шести дней пути от главного войска, чтоб лошади и верблюды могли удобнее прокормиться. Русские взяли обоз, при котором нашли 60000 лошадей, 200 аргамаков, 80 верблюдов, и прислали Шереметеву 20 языков, которые сказали ему, что хан идет к Туле; Шереметев продолжал идти за ним следом, но в это время хан уже узнал о царском походе и возвратился назад. В 150 верстах от Тулы, на Судбищах, встретился он с отрядом Шереметева, который, несмотря на малочисленность своего войска, ослабленного уходом трети ратных людей на крымский обоз и еще не возвратившихся, вступил в битву, бился с полудня до ночи, потоптал передовой полк, правую и левую руку, взял знамя князей Ширинских. Но татары не ушли; надобно было приготовляться к новой битве на другой день, и Шереметев послал гонцов к тому отряду, который ходил на обоз, чтобы спешил к нему на помощь, но из этого отряда прискакали к утру только немногие, остальные с добычею отправились в ближайшие русские города, кто в Рязань, кто в Мценск. Между тем хан ночью пытал двоих русских пленников: хотелось ему дознаться о числе войска, так храбро бившегося с ним днем; один из пленников не вытерпел мук и рассказал, что у Шереметева людей мало и тех целая треть отпущена на татарский обоз. Ободренный этим известием, хан на рассвете возобновил битву; бились до полудня; сначала и тут русские успели разогнать крымцев и около хана оставались только янычары, но воевода Шереметев был тяжело ранен и сбит раненым конем; русские замешались без воеводы и потерпели сильное поражение, только двум воеводам, Басманову и Сидорову, удалось собрать около себя тысяч с пять или шесть ратных людей и засесть в лесном овраге; три раза приступал к ним хан со всем войском и всякий раз без успеха; наступил вечер; хан, боясь приближения русского войска, оставил Басманова и Сидорова в покое и поспешил переправиться за Сосну; русские потеряли в Судбищенской битве 320 детей боярских и 34 стрельца. Царь переправился уже чрез Оку и приближался к Туле, когда ему дали знать, что Шереметев поражен и хан идет к Туле; мнения разделились между воеводами: одни говорили, что надобно идти назад, за Оку, и оттуда к Москве, другие говорили, что не должно обращать тыла перед врагом и помрачать прежнюю славу: хотя хан и одержал победу над Шереметевым, однако войско его утомилось, потеряло много убитыми и ранеными, потому что битва была упорная, двухдневная. Царь принял последнее мнение и продолжал поход к Туле, но, пришедши туда, узнал, что хан спешит в Крым, делает по 70 верст в день и догнать его нельзя, потому что между ним и царем уже четыре дня пути. Простоявши в Туле два дня, дождавшись сбора всех своих ратных людей, Иоанн возвратился в Москву.