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