Уходя в степи, Ахмат, как и Едигей в свое время, чтобы сохранить лицо, направил московскому князю письмо, требуя дани и повиновения, угрожая в противном случае новыми набегами и всевозможными карами. Но дни самого Ахмата были сочтены. Прознав, что золотоордынский хан возвращается с богатой добычей, ханы Тюменской и Ногайской Орд, объединившись, на одной из стоянок напали на его ослабленное холодом и бескормицей войско, убили самого хана, а литовскую добычу, включая множество пленников, поделили между собой.
В будущем Золотая Орда, еще более раздробленная сыновьями Ахмата, хоть и доставляла кое-какое беспокойство Московскому княжеству, но серьезной угрозы его национальной безопасности уже не представляла. Тем не менее, по обычаям раннего евразийского Средневековья, не только Иван III, но и его преемники продолжали нести большие материальные издержки на «покупку мира» у своих неспокойных соседей, посылая различным ханам, в том числе и своим касимовским вассалам, дорогие поминки (подарки) за счет средств, собираемых для этих целей с населения. Была даже четко определенная сумма расходов на эти цели — тысяча рублей в год, причем 717 рублей из великокняжеской казны, остальные за счет удельных князей.
Последующие десятилетия отношения Московской Руси со Степью строились в основном по схеме: Москва — Казань — Крым.
Так что же Казань? Через год после Стояния на Угре умирает казанский хан Ибрагим, сын первооснователя Казанского ханства Махмудека. Престол наследует Али-хан, его сын от одной из второстепенных жен. Но такое развитие событий не устраивает старшую жену Ибрагима, промосковски настроенную Нур Салтан, ставшую вскоре старшей женой крымского хана Менгли-Гирея и мечтавшую увидеть на казанском троне своего сына Мухаммед-Эмина. Начинается упорная борьба сторонников противостоящих партий. Не остается в стороне от этой борьбы и Москва. В 1487 году Иван III отправляет под стены Казани многочисленную рать во главе с князем Даниилом Холмским (тверская ветвь Рюриковичей). После двухмесячной осады Али-хан сдается, и на трон возводится Мухаммед-Эмин, чья вассальная зависимость от московского князя, как и зависимость его брата Абдулатифа, занимавшего некоторое время казанский трон, не подвергалась сомнению вплоть до самой смерти Ивана III.
Это было первое покорение Казани, после которого авторитет Москвы в глазах восточных правителей заметно вырос. Уже в 1490 году Иван III принимает посольство Герата. В том же году он заключает союз с ногайскими мурзами против «сыновей Ахмата», владевших осколками некогда могущественной Золотой Орды. Через два года он как «защитник всего православного христианства» принимает посольства кахетинского царя Александра, а еще через год и сам направляет посольство в далекий Египет.
Отношения Москвы с Крымским ханством складывались на фоне их враждебных отношений с Литвой и Волжской Ордой и с учетом утвердившейся турецкой гегемонии во всем Черноморском бассейне. Следует сказать, что Оттоманская Турция, возникшая на руинах Византийской империи, к тому времени владела морскими проливами, устьями Дуная и Днестра, Крымом и Таманью, из чего следовал совершенно естественный вывод, что султан единолично и по своему усмотрению распоряжался ключами от морских ворот Молдавии, Венгрии, Польши, Татарии и Руси. А поскольку крымский хан считался вассалом Турции, ибо власть получал из рук турецкого султана, то и политику он проводил соответствующую, а именно: не допустить, чтобы у католической Европы, которую турки вознамерились захватить, появился союзник в лице Московской Руси. И как бы это ни показалось парадоксальным, но общность врагов в лице Литвы и Волжской Орды на время сделала крымских татар — потомков недавних злейших врагов всех русских земель, иноверцев — чуть ли не единственными союзниками Московского княжества.
Увы, но союз этот, выгодный Москве, был крайне невыгоден другим русским землям, и в первую очередь православным южнорусским провинциям Литовского княжества, которые с молчаливого согласия, а то и по прямому указанию Ивана III подвергались беспощадным набегам крымских татар. Результатом одного из таких татарских рейдов было полное разрушение Киева, пленение и продажа на невольничьих рынках практически всех уцелевших жителей «матери городов русских» (1482 г.).
Но не нужно думать, что в разрешении спора между Москвой и Литвой за западно-русские земли Иван III опирался только на «иноверцев» и не пытался найти третейского судью или союзника в лице христианских королей. Поиск таковых велся достаточно активно. Так, в 1482 году московский князь обменялся посольствами с Венгрией, для того чтобы выработать совместные мероприятия против агрессивной политики короля Казимира. Переговоры, к сожалению, не достигли желаемого результата по независящим от сторон обстоятельствам. Через год Иван III договаривается о браке своего сына Ивана Молодого и дочери Стефана Молдавского Елены. Он понимает, что этот шаг накладывает на него серьезные обязательства по защите новых родственников-единоверцев, но идет на это сознательно в расчете на приобретение хоть и слабого, но стратегически важного союзника — на случай разногласий с крымскими татарами, венграми и поляками. В конце 1480-х годов Москва ведет активные переговоры с Германской империей. От королевской короны, принятие которой означало бы автоматическое вхождение Московии в систему Священной Римской империи, Иван III с присущим ему чувством собственного достоинства отказывается, предлагая заключить союзный договор. И вроде бы все шло к благополучному завершению, но в самый последний момент император отдал предпочтение Литве, и договор не вступил в силу.
Оставалось последнее средство урегулировать русско-литовские отношения — династический брак. И Иван III решает им воспользоваться. В 1493–1494 годах он ведет трудные и упорные переговоры о прекращении пограничной войны, которые завершаются… браком дочери Ивана III Елены и великого князя литовского Александра, сына Казимира. Это был безусловный дипломатический успех Москвы. Литва впервые признала за Иваном III право именоваться Государем всея Руси и отказывалась от притязаний на Новгород, Псков, Тверь, Рязань, Ржев, Вязьму, Алексин. Но это еще не означало, что Казимир признал и нелегитимность своей власти на западно-русских землях. Киев, Витебск, Полоцк, Гродно и другие ныне белорусско-украинские земли он считал чуть ли не своими «отчинами» и «дединами». Более того, подыгрывая дипломатической игре, московский князь притворно уступил Александру право владеть Смоленском, Любутском, Брянском и Мценском.
Однако мир длился недолго. После гибели от рук крымских татар киевского митрополита Макария (1497 г.) великий князь литовский назначил на его место смоленского епископа Иосифа, родственника перешедшего в католичество Яна Сапеги, который чуть ли не сразу по восшествии на митрополичью кафедру начал переговоры с папским двором об объединении церквей. Кроме того, вопреки заключенному русско-литовскому договору, римско-католическое польское духовенство не только вело наступление на права православной части населения Литвы, но и настаивало на принятии католичества дочерью Ивана III, великой княгиней литовской. Но это годилось лишь для дипломатических демаршей, поводом же активных действий стал отъезд из Литвы двух русских князей — Семена Можайского и Василия Шемячича, потомков злейших врагов Василия Темного, недовольных католическим засильем. Это придало последующим действиям московского князя благородный смысл — защита православия и православных христиан.
Согласовав с Менгли-Гиреем свои притязания на Киев и Черкассы, Иван III в мае 1500 года объявил Литве войну, которая ознаменована лишь победой московских войск под командованием прапрадеда первого русского царя династии Романовых Юрия Захарьевича Кошкина на берегах реки Ведроши да неудачной осадой Смоленска. На этом желание воевать как у той, так и у другой стороны иссякло. За неимением взаимоприемлемых условий для «вечного» мира в апреле 1503 года было заключено перемирие на шесть лет, выгодное Москве. Под юрисдикцией московского князя на все это время оставались вотчины Семена Можайского и Василия Шемячича, а именно большая часть Черниговско-Северской земли (бассейны рек Десна, Сож, Сейм), а также Брянск, Мценск, Любуцк, Дорогобуж, Любеч и ряд других городов, расположенных в верховьях Оки.