То, что Москве удалось расширить зону своего влияния на юг и восток, во многом – особенно поначалу – было результатом ее взаимоотношений с Крымским ханством. В то время Крымское ханство занимало территорию Крымского полуострова и большой кусок Кипчакской степи к северу от него. Крымские татары вели более оседлый образ жизни, чем их предшественники из Золотой Орды, но в основе их экономики по-прежнему лежали набеги и торговля. Благодаря торговле в крупных крымских городах существовали большие немусульманские общины; Русское государство также вело оживленную торговлю через степь. Политическая стабильность и военная мощь Крыма зависели от способности хана (из династии Гиреев, потомков Чингисхана) добиваться поддержки и сотрудничества от его беев – вождей знатных кланов.
По инициативе Крыма между Москвой и Крымским ханством был заключен взаимовыгодный военный союз, продлившийся почти 40 лет – с 1480 по 1519 год. В ответ на это Великое княжество Литовское заключило стратегический союз с Большой Ордой, которая все еще пыталась возродить былую славу и мощь Золотой Орды. Эти два союза часто конфликтовали друг с другом, и зачастую успех был на стороне крымско-московской коалиции. Одно из таких событий, заслуживающее отдельного упоминания, произошло в октябре 1480 года, когда войска Большой Орды в ожидании своих литовских союзников расположились на южном берегу реки Угры, предполагая после ледостава выступить в поход на московские земли. Силы Ивана III заняли противоположный берег. Однако восстание православных князей и набеги крымских татар с юго-востока отвлекли литовские войска и не позволили им присоединиться к ордынской армии. В то же самое время глава Большой Орды хан Ахмат получил известия о готовящемся нападении со стороны ногайских татар и вынужден был увести свои войска назад, не вступая в битву с Иваном. Это так и не случившееся сражение в символическом смысле стало важнейшей победой Русского государства, хотя, вопреки распространенному мнению, оно и не означало окончание монгольского ига. Последовавшее за этой неудачей ослабление Орды было на руку и крымскому хану. Крым, чьи правители с 1475 года стали вассалами Османской империи (непокорными), помог Москве установить дипломатические отношения со своим сюзереном. В качестве ответной услуги Русское государство постоянно вмешивалось в казанские междоусобицы, что в итоге привело к воцарению династии Гиреев и на ханском престоле Казани [Сыроечковский 1932: 200–204, 217, 224; Khodarkovsky 2002: 77–91; Ходарковский 2019; Martin 1983: 443–445]. Поддерживая навязанных Крымом казанских ханов, Москва добилась того, что в конце XV и начале XVI века на западе степи возник тройственный союз, который мог полностью доминировать на этих территориях.
Однако к 1510-м годам Москву и Крым перестали связывать общие интересы, и их отношения из союзнических превратились во враждебные. Прежде всего увеличение размеров и мощи Русского государства привело к изменению баланса сил. Постоянные завоевания Москвы и рост торговли ослабили позиции Крымского ханства как посредника в степных делах: теперь великий князь Московский обладал достаточным влиянием, чтобы попытаться посадить на казанский престол собственного ставленника и вести дела с Османской империей напрямую. Кроме того, и Крымское ханство, уничтожив в начале XVI века Большую Орду, решило ту задачу, из-за которой оно во многом и было ранее заинтересовано в сотрудничестве с Москвой [Martin 1983: 447; Khodarkovsky 2002: 91–100; Ходарковский 2019]. В 1519 году Крым объявил о разрыве союза с московским князем; теперь Гиреи стали временными союзниками Великого княжества Литовского. В результате Москва обрела в лице Крымского ханства могущественного врага по ту сторону степи. Южные границы Русского государства были уязвимы. Ее степной враг состоял в союзе с обладавшей огромной военной мощью Османской империей. Кроме того, теперь Крым и Москва соперничали за влияние на Казанское ханство.