Впрочем, эти неудачи не обескуражили Шейх-Мамая. Ещё в октябре 1548 г. в Москву прибыли послы от бия и высших мурз, которые после продолжительных переговоров заключили с царём договор о ненападении и помощи России против её врагов. Кроме того, было достигнуто соглашение о совместном выступлении против Астрахани, где ногайцы предлагали посадить на престол находящегося в Москве бывшего астраханского хана Дервиш-Али. 5 февраля 1549 г. послы были отпущены восвояси в сопровождении русского посла к Шейх-Мамаю, Ивана Борисовича Федцова. Но прибывший в орду русский посол не застал Шейх-Мамая в живых. А новый бий Юсуф отказался утвердить привезённый договор. Более того, потребовал от русских, чтобы те воздавали ему такой же почёт и уважение, каким пользовались крымский хан и бывшие золотоордынские государи. На что Москва, соответственно, ответила отказом. Начавший было складываться направленный против Крыма русско-ногайский союз рухнул так и не образовавшись. Но, несмотря на это, в Москве уже и не думали о сворачивании операции по захвату Астрахани. Тем более, что не все ногайские мурзы были согласны со своим новым бием. Младший брат Юсуфа, руководитель Правого (Западного) крыла Ногайской орды нурадин Исмаил, будучи в экономическом плане сильно зависим от торговли с Русским государством, отказался поддержать политику Юсуфа и продолжал побуждать Ивана IV на войну с Астраханью с целью возвращения престола Дервиш-Али.

Москва, понятное дело, не могла упустить такой шанс. Между царём и нурадином было заключено соглашение о совместном выступлении и летом 1549 г. Дервиш-Али был послан в Астрахань, а с ним воевода кн. Владимир Иванович Воротынский с 10-тысячным войском. Выступив из Нижнего Новгорода, к 27 июня войска на судах подошли к району Переволоки — месту наибольшего сближения Волги и Дона, где по плану должны были соединиться с ратью Исмаила. Но ногайцев там не оказалось, так как узнав, что Исмаил собирается принять участие в завоевании русскими астраханского юрта, Юсуф-бий собрал армию и двинулся к Волге. И Исмаил с отрядами преданных ему мурз был вынужден выступить ему на встречу. Так и не дождавшись обещанной нурадином ногайской конницы, русские продолжили поход самостоятельно.

Первое боевое столкновение русских войск с астраханцами произошло 29 июня у Черного Яра. Передовые отряды Ямгурчи были разбиты наголову. Пленные показали, что ханская ставка находится не в самой Астрахани, а в пяти верстах от города, в одном из рукавов дельты Волги, и что гарнизон в самой крепости крайне незначителен. Имея эти сведения, часть русского войска во главе с кн. Юрием Ивановичем Шемякиным-Пронским блокировала Ставку хана, а другая часть во главе с кн. Владимиром Воротынским без боя заняла Астрахань 2 июля 1549 г.

Узнав о падении своей столицы хан Ямгурчи в тот же день бежал к своим союзникам на Кавказ. Русские войска бросились в преследование и 7 июля настигли беспорядочно отступавшие ханские силы, без особого труда перебив их, а частично — захватив в плен.

Согнав Ямгурчи русские поставили в Астрахани ханом Дервиш-Али, который, по условиям договора, признавал себя вассалом Русского государства и обязывался выплачивать ежегодную дань в размере 40 тыс. алтын (1200 руб. серебром) и 3 тыс. осетров в сажень (до 2,5 метров). Кроме того, русские получили право вести рыбную ловлю от Казани до Астрахани — по всей Волге — беспошлинно и безъявочно (т. е. не извещая об этом и не спрашивая разрешения астраханских властей). После чего, достигнув таким образом поставленных целей, русские 29 июля покинули Астрахань, оставив в ханстве под началом Петра Дмитриевича Тургенева контингент русских войск для предотвращения восстания местного населения против хана Дервиш-Али, как русского ставленника, восстановив власть Москвы над Нижним Поволжьем.

Однако ограничиваться только этим в России уже не собирались. Череда успехов в борьбе против "басурман" вызвала у многих "головокружение от успехов" и породила планы продолжения наступления в южном направлении с целью сокрушения Крымского ханства и присоединения к Русскому государству Северного Кавказа. Все условия для этого, казалось, складываются максимально благоприятно. В возникшей в Ногайской орде междоусобице между бием и нурадином осенью 1549 г. погиб Юсуф и во главе ногайцев стал дружественный русским Исмаил. Турецкий султан Сулейман, после заключения в 1547 г. перемирия с императором Священной Римской империи и венгерским королём, считая тыл обеспеченным, начал в 1548 г. войну с Ираном. Весной 1548 г. турки, совершив дальний рейд в Иран, заняли Азербайджан, взяли Тебриз и, разбив шахские войска в битве при Маранде, углубились в Иран до Кашана и Кума. В том же году они вторглись в Восточную Армению, в 1549 году — в Южную Грузию. Но эти успехи потребовали крайнего напряжения сил огромной Османской империи. Уже в 1549 г. французский посол сообщал, что своим персидским предприятием султан подвергает своё государство опасности, что потери в войске очень велики, что в янычары берут мальчиков 14 лет, и что не хватает для войска лошадей. Таким образом, это порождало надежды на то, что завязшая в войне на востоке Османская империя не сможет заступиться своего вассала, поскольку скорее ей самой требовалась поддержка крымцев, а возможность оказания помощи последним со стороны турок становилась сильно ограниченной.

Под влиянием этих факторов в Москве сложилось мнение закрепить достигнутые успехи и довести борьбу с татарскими ханствами до конца. Уже в 1550 году, сразу после установления русского протектората над Астраханью, было принято решение об организации похода на Крым, который должен был завершиться "посажением" на ханский престол царевича Джан-Темира, сына Дервиш-Али. Царь и его советники не могли не понимать, что такой поход на Крым означает вторжение в непосредственную сферу турецких интересов. Ведь крымские ханы, как уже указывалось выше, были вассалами турецкого султана, в Крыму и на подступах к нему стояли турецкие крепости. Радикально решить крымскую проблему было невозможно без столкновения с Османской империей.

В связи с этим всё более остро вставал вопрос о возможных союзниках Русского государства. Прежде всего внимание русских политиков обращалось к Польско-Литовской державе и особенно к непосредственно граничившему с Россией Великому княжеству Литовскому. В Москве хорошо знали о том огромном ущербе, который наносили постоянные набеги крымских татар южным областям Литвы и Короны Польской, и о той необъявленной войне, которую население этих областей вело уже много десятилетий, отражая натиск агрессоров. Казалось, что план совместного выступления России и Литвы, чтобы раз и навсегда ликвидировать татарскую опасность, должен встретить в Великом княжестве Литовском большую поддержку. И по мере того как планы наступления на Крым становились всё более реальными, в русской внешней политике чётче обозначалась тенденция к поискам союза с Литвой против крымцев и турок. После установления русского протектората над Астраханью (1549 г.) в Вильно со специальным извещением о победе был отправлен гонец, которому предписывалось говорить пока ещё неофициально о желании царя "соединачася" с Сигизмундом II Августом "христианство от бессерменских рук отвселе свобожати". Когда в январе 1550 г. в Москву прибыл с поздравлениями по поводу победы над "неверными" литовский посланец Юрий Тышкевич, вопрос о союзе между государствами был поставлен уже в официальном порядке.

Эти первые попытки нащупать путь к согласию с Литвой против татар не привели, однако, к положительным результатам. Сигизмунд II и его ближайший советник Николай Радзивилл Чёрный были далеки от каких-либо планов сотрудничества с Россией и, наоборот, прилагали усилия к сохранению дружественных отношений с Крымом, тем более что с концентрацией сил Крымского ханства на борьбе с Россией татарские набеги на южные области Польско-Литовского государства практически прекратились. На состоявшихся в Москве в январе 1551 г. переговорах литовские послы охотно говорили о необходимости соединения христиан для борьбы против неверных, но использовали это лишь как аргумент в пользу продления перемирия между государствами, тщательно уклоняясь от обсуждения каких-либо других вопросов.

Неудача настигла русскую дипломатию в попытке привлечь к замышляемому походу на Крым ногайцев. Прибывшие в начале 1550 года в Сарайчук (столицу Орды) русские послы предложили бию Исмаилу послать вместе с русским войском шесть тысяч ногайской конницы во главе со своими сыновьями и племянниками, которые в случае успеха должны были осесть в Тавриде и сформировать новую крымскую аристократию. А если понадобится, то и послать осенью на крымцев основные ногайские силы. Но и это замысел не увенчался успехом по причине внутренних неурядиц в Ногайской орде.

Сыновья погибшего бия Юсуфа бежали в Крым, где "пристали к крымскому царю". Получив такое подкрепление Сахиб Герай тут же принялся строить планы похода к занятой русскими Астрахани, возвращения тамошнего трона Ямгурчи. Одновременно с этим шла подготовка к большому набегу на Русь, с целью отвлечения внимания Москвы от событий в Нижнем Поволжье.

Весной (марте-апреле) 1550 г. Ямгурчи вместе с Юсуфовичами и отрядом выделенных ему крымским ханом пищальников-тюфенкчи подступил к Астрахани. Но его попытка вернуть себе престол не увенчалась успехом. Дервиш-Али при поддержке русского гарнизона успешно отбил нападение. Но Ямгурчи на этом не успокоился. В мае он снова подступил к городу, но и на этот раз его ждала неудача. Дервиш-Али к этому времени решил переориентироваться с Москвы на союз с Крымом и сменил свою внешнюю политику. Из Бахчисарая пригласил к себе на должность калги-султана царевича Хаспулад Герая, а сыновьям Юсуфа обещал помогать против Исмаила. Обрадованные Юсуфовичи отстали от Ямгурчи и "побили" его, с астраханским же правителем заключили шертное соглашение о союзе против бия. Дервиш-Али помог им переправиться через Волгу на Ногайскую сторону, дав им возможность начать новый виток борьбы за власть у ногайцев.

Внезапным ударом сыновья Юсуфа и их сторонники захватили ногайскую столицу, где убили враждебного им главу семейства Шихмамаевичей (потомков Шейх-Мамая) Касима-мурзу. А через два дня обрушились на кочевье семьи Исмаила, в их руках оказались всё имущество и стада. В Ногайской орде вновь заполыхала гражданская война.

Пришли тревожные известия и с юга. В конце 1549 г. Сахиб Герай и его советники приняли решение предпринять новый набег на Русское государство. Стремясь усыпить бдительность противника крымский хан возобновил с Москвой мирные переговоры, и распустил слух о подготовке похода на черкесских князей. Тем не менее, в Москве от своих "доброхотов" в ханстве (где целые знатные семейства находились "на жаловании" от русской казны, за что должны были сообщать русским о намерениях своего хана и влиять на его решения в пользу Русского государства) получили более или менее достоверную информацию о направлении готовящегося выступления и с началом весны 1550 г. начали размещение войск вдоль южной границы с целью отражения ожидаемой атаки крымцев.

Однако, в отличие от прошлых лет, только этим в Москве решили не ограничиваться. В начале июня 1550 г. собранное в Белёве 10-тысячное русское войско под командованием Ивана Васильевича Шереметьева выступило в поход в сторону крымских владений. Формальной целью похода был захват татарских табунов, что паслись на так называемом Мамаевом лугу на левобережье Днепра в его низовьях, и одновременно стратегическая разведка намерений крымского хана. Фактическая задача же состояла в том, чтобы заблаговременно обнаружить крымское войско, сопроводить его до русских пределов и здесь атаковать с тыла, сковав до подхода главных сил "береговой" рати и Государева полка. Рать Шереметьева должны была стать "наковальней", на которую обрушился бы "молот" главных сил русской армии.

Составленная из трёх полков рать шла на юг Муравским шляхом. В верховьях рек Мжи и Коломака (приток р. Воркслы), где войско должно было соединиться с почапским отрядом, Шереметьев узнал, что "царь крымский Донец перелез со многими людьми, а идет к рязанским и тульским украйнам". Получив это известие, воевода немедленно развернул свои силы назад и скорым маршем пошёл обратно на север по Муравскому шляху к Думчеву кургану, у истоков Псла (севернее нынешней Прохоровки).

Тем временем известия о происходящем в Поле достигли Москвы. 28 июня к Ивану IV прибыло сразу несколько гонцов, которые сообщили царю о том, что татары во множестве "лезут" через Северский Донец.

Эти новости привели в действие русскую военную машину, шестерни которой начали проворачиваться во всё убыстряющемся темпе. Командующие русской ратью немедленно были "отпущены" царём к своим войскам. В Москве начался сбор Государева полка. 2 июля царь прибыл в Коломну, где к этому времени сконцентрировались главные силы русского войска, и откуда 4 июля началось выступление в сторону Тулы, к которой, по поступавшим сообщениям, двигались крымцы.

Однако вскоре пришли известия о том, что ситуация изменилась. Сахиб Герай узнав от захваченных пленных о выдвижении русской рати повернул сначала к Одоеву, а затем, не доходя до города около 30 вёрст, развернулся назад в степь, явно пытаясь уклониться от столкновения с основными русскими силами. Однако царь тем не менее, рассчитывая на то, что, повернув назад, хан наткнётся на Шереметьева, тот "свяжет" татар и тогда решающий бой всё же состоится, решил продолжить марш в прежнем направлении. Но уже спустя всего несколько часов поступили новые сообщения, после получения которых царю и его окружению стало ясно, что первоначальный план окружения и разгрома крымского войска окончательно рухнул.

Определив маршрут движения крымского войска, насчитывавшего более 30 тыс. бойцов, и повернув вдогонку за Сахиб Гераем, Шереметьев, как он позднее докладывал царю, предполагал "...его (т. е. Сахиб Герая) в войне застати: нечто станет воевати и розпустит войну, и воеводам было приходити на суволоку, а не станут воевати, и им было промышляти, посмотря по делу..." И на первых порах всё развивалось так, как предполагал воевода. Хан, не догадываясь о своих преследователях, быстро шёл на север. Приблизившись к русской границе на реке Сосна, в районе т. н. Кирпичного брода, Сахиб Герай дал своему войску отдых и здесь оставил свой обоз ("кош") вместе со значительной частью заводных коней, максимально облегчив своё воинство перед последним броском.

Длившаяся несколько дней остановка татарского войска позволила Шереметьеву нагнать неприятеля. Когда основные силы Сахиб Герая 29 июня двинулись скорым маршем (примерно 50 и даже более километров в сутки) двинулись на Тулу, Шереметьев, к этому времени прочно "повисший" у него на хвосте, решил атаковать ханский обоз. 1 июля посланные им силы взяли "царёв кош" и вместе с ним богатую добычу, насчитывавшую шестьдесят тысяч лошадей и восемьдесят верблюдов.