Частичное решение проблемы с Казанским ханством позволило Ивану III уделить больше внимания Литве. В 1487-м и в последующие годы с ней имели место пограничные инциденты в Смоленской земле и в районах верховских городов. Официально Москва в эту «малую войну» вовлечена не была, поскольку инициатива принадлежала сыну Ивана III — тверскому князю Ивану Молодому, брату Ивана III — углицкому и можайскому князю Андрею Большому и волостелям районов, прилежащих к верховским городам. В целом во время этих столкновений верх брали московиты, которые во время своих набегов захватывали тысячи людей, угоняли их в Московию и там расселяли. Необходимо заметить, что некоторые князья как в районе Вязьмы, так и в верховских городах находились в оппозиции Казимиру и требовали расширения своих прав и привилегий. Иван III, проводивший у себя в Московии политику централизации, поддерживал их требования и добился того, что несколько русских князей верховских городов, среди них Воротынские и Белевские, перешли на сторону Москвы.
Одновременно дипломатия Ивана готовила почву на случай, если «малая война» перерастет в большую. Помимо переговоров с Венгрией он налаживал связи со Священной Римской империей. В 1486 году Москву посетил немецкий князь Николай Поппель. В 1489 году он вновь приехал в Москву в качестве официального посла императора Фридриха III, чтобы предложить Ивану III королевскую корону. Согласие Ивана III означало бы включение Московии в систему Священной Римской империи. Иван III от короны отказался, однако выразил желание заключить с империей союзный договор. После обменов посольствами сын Фридриха III — король Максимилиан I — этот договор одобрил (1491), но вслед за этим заключил мир с сыном Казимира Владиславом, королем Богемии и Венгрии. Союз с Москвой после этого потерял для него значение, и договор не вступил в силу.
Контакты со Священной Римской империей в те годы благотворно повлияли на развитие на Руси горного дела. Еще в 1482 году Иван III просил короля Матвея Корвина Венгерского направить в Москву горных инженеров для разведки месторождений металлов. Если венгерские инженеры и были посланы, то они не добрались до Москвы. В 1491 году послы Ивана III привезли двух горных специалистов из Германии. В русских источниках упоминаются только их имена — Иван и Виктор. Сопровождаемые двумя русскими чиновниками, они отправились в Северную Русь и разведали месторождения серебра и меди в Усть-Цильме в низовьях реки Печоры. В следующем году в Москву приехал немец Михаил Снапс с рекомендательными письмами от короля Максимилиана I и его дяди эрцгерцога Сигизмунда Инсбрукского, которые просили Ивана III позволить Снапсу предпринять путешествие к берегам реки Оби для географических исследований. Иван III отказал под предлогом, что не сможет гарантировать безопасность Снапса в «варварских» районах. Но скорее всего, дело было в подозрениях по поводу истинной цели миссии Снапса.
Таким образом, только крымский хан Менгли-Гирей оказался для Ивана III полезным союзником в противостоянии с Литвой, хотя и на него не всегда можно было положиться. В 1492 году Менгли-Гирей решил возвести на северной стороне днепровской дельты крепость Очаков, которая служила бы форпостом для будущих походов на Польшу и Литву. Известие об этом вызвало большое волнение в Польше и Литве. В Москве новость встретили, скорее всего, со смешанными чувствами. Цитадель, без сомнения, укрепляла положение Менгли-Гирея относительно западных врагов Москвы. В то же время Очаков можно было рассматривать и как постоянную угрозу Киеву и другим украинским землям, на которые Иван III имел собственные виды.
В конце концов крепостью овладели турки, и она служила им важной базой в войнах с Россией в конце XVII и в XVIII веке. В 1788 году русские взяли ее штурмом и присоединили к России по Ясскому договору 1792 года. Захват русскими Очакова вызвал крайнее недовольство Великобритании. Американский историк Дж. Х. Глиссон высказывает мнение, что именно это событие положило начало русофобии в Англии.
7 июня 1492 года в Гродно умер Казимир. Он оставил несколько сыновей, старший из которых, Владислав, был королем Богемии (с 1471 года) и Венгрии (с 1490 года). Яна-Альбрехта после смерти Казимира избрали королем Польши, а следующий по старшинству, Александр, стал великим князем Литовским. Позже, в 1501 году, после смерти Яна-Альбрехта Александр занял также польский трон, оставаясь при этом великим князем Литовским.
Необходимо сделать несколько замечаний в связи с изменением после смерти Казимира политики Литвы в отношении иудеев. В XV веке евреи составляли существенную часть городского населения в Польше и Литве. В XIII и XIV веках польские короли издали несколько указов, позволявших евреям свободно заниматься торговлей на всей территории Польши. В XV веке Казимир подтвердил старые указы и даровал евреям несколько новых привилегий, несмотря на то что католическая церковь постоянно стремилась ограничить их права. При этом существовало недовольство ростовщичеством евреев, что привело к запрещению в 1454 году давать ссуды под проценты, однако этот акт имел юридическую силу только на территории Польши.
В Литве на всем протяжении правления Казимира евреи пользовались теми же привилегиями, что и в Польше. Необходимо отметить, что караимские поселения подчинялись тем же законам, что и евреи-раввинисты. По Магдебургскому праву караимские общины Тракая обладали правами, которые в других случаях предоставлялись только христианам.
Но в 1492 году, после смерти Казимира, евреям запретили жить в Ковно. Три года спустя великий князь Александр издал указ, по которому как евреи-раввинисты, так и караимы изгонялись из Великого княжества Литовского. Это частично можно считать результатом влияния на Александра римско-католического духовенства. Но вместе с тем существует вероятность, что советники Александра считали евреев потенциальными агентами Ивана III. Следует заметить, что Александр аннулировал свой антисемитский указ в 1503 году — то есть тогда, когда духовенство русской православной церкви преодолело сопротивление «заволжских старцев», что предопределило ограничение деятельности проповедников и других течений, в том числе «жидовствующих».
В 1493 году Литва и Москва начали переговоры, дабы положить конец невыносимой ситуации необъявленной пограничной войны. Ради улучшения взаимоотношений литовцы предложили соединить браком дочь Ивана III Елену с великим князем Литовским Александром. На этих переговорах Иван III впервые в отношениях с зарубежным государством назвал себя «государем Всея Руси». Эта формулировка не была его изобретением. Предок Ивана III — Иван I Калита (великий князь Владимирский в 1328–1237 и 1339–1340 годах) включил ее в свою титулатуру, следуя образцу титулов русских митрополитов. Позднее она несколько раз появлялась в титуле московских великих князей в межкняжеских договорах, как, например, в договоре великого князя Московского Симеона с братьями (приблизительно в 1350 году); в договоре Василия II с братом Юрием (приблизительно в 1390 году); в нескольких договорах Ивана III с удельными князьями (в 1483–1486 годах). Нов 1493 году Иван III впервые включил выражение «Всея Руси» в свой титул на переговорах с иностранным государством, и, что особенно важно, на переговорах со страной, относительно которой оно звучало как вызов, поскольку правитель этой страны сам имел слово «Русь» в своем титуле (Великий Князь Литовский и Русский).
После продолжительных споров договор о дружбе и взаимопомощи между Москвой и Литвой был подписан в Москве 7 февраля 1494 года. Литовцы согласились титуловать Ивана III «государем Всея Руси». Александр и Иван III дали обязательства не вторгаться во владения друг друга. Александр отказался от притязаний на Новгород, Псков, Тверь, Ржев, Вязьму, Алексин и Рязань. Иван III — от притязаний на Смоленск, Любутск, Мценск и Брянск. Что касается удельных русских князей верховских городов, то Александр снял вассальную зависимость с Одоевских, Воротынских, Белевских и одной ветви Мезецких. Иван со своей стороны согласился признать сюзеренитет Александра над другой ветвью Мезецких.
Договор в целом, безусловно, был более выгоден Москве, чем Литве. Правда, большая часть из того, что передал Александр, в действительности ему не принадлежала (Новгород, Псков, Тверь, Рязань), однако он вместе с тем вынужден был отказаться от важной части спорной пограничной территории, включая Вязьму и часть верховских городов. Более того, ему пришлось признать титул Ивана III «Всея Руси» без точного знания того, что под ним подразумевается.
Очевидно, что литовцы пошли на столь значительные уступки в надежде обеспечить прочный мир на своей восточной границе. Они полагали, что брак Александра с дочерью Ивана сделает отношения между двумя правителями более дружелюбными. Помолвка Елены с Александром состоялась в преддверии подписания политического договора. Александр был представлен доверенным лицом. Главным условием Ивана III было сохранение его дочерью православной веры. Но даже после помолвки многие детали оставались еще не оговоренными, и только одиннадцать месяцев спустя литовские посланники прибыли в Москву (6 января 1495 года), чтобы доставить невесту в Вильно. Иван III со своей стороны поручил сопровождать Елену князю Семену Ивановичу Ряполовскому и нескольким московским боярам с женами. В группу сопровождающих включили также московского священника Фому, которому предстояло исполнять в Вильно роль духовника Елены. Свадебный поезд покинул Москву 13 января.
Путешествие Елены в Вильно и ее свадьба живо описаны в отчете московских послов Ивану. Когда поезд Елены добрался до нового владения Московии Вязьмы, его торжественно встретили князья Вяземские с богатыми дарам. Не менее сердечный прием ожидал Елену и в Смоленске, первом крупном городе на территории, принадлежащей Литве. Ее приветствовали наместник Александра, все бояре и жители города, а также русское духовенство. Елена пробыла в Смоленске два дня и присутствовала на службе в русском кафедральном соборе.
Подобным образом Елену принимали и на пути через западнорусские земли Великого княжества Литовского — в Полоцке и Витебске. Когда она прибыла на литовскую территорию, близ Крево ее встретили представители Александра — князь Константин Иванович Острожский и князья Иван и Василий Глинецкие. Они предложили Елене для продолжения пути роскошную карету, посланную Александром. Карету везли восемь серых жеребцов в прекрасной сбруе. Однако Елена имела строгие указания отца воспользоваться каретой (предложение которой, по-видимому, ожидалось), только если в ней будет находиться мать Александра. Поскольку этого не случилось, Елена отказалась пересесть в литовскую карету и осталась в тапкане — крытой повозке, в которой она ехала из Москвы. За две мили до Вильно невесту встретил Александр верхом на коне. Подъехав к тапкане, он приказал постелить на землю между его конем и повозкой Елены красную материю. Московские бояре, недолго думая, положили поверх материи у тапканы кусок Дамаска (шерстяной ткани). Таким образом, когда жених спешился, а Елена вышла из повозки, он ступил на свою материю, а она на свой Дамаск — то есть символически она осталась на московской территории.
После взаимных приветствий Елена продолжила путь в тапкане, а Александр сопровождал ее верхом. По приезде в Вильно Елена отправилась в русскую церковь Рождества Богородицы, а Александр — в римско-католический собор, где должно было состояться бракосочетание. У входа в русскую церковь Елену приветствовал православный митрополит Киевский Макарий. Потом по старому русскому свадебному обычаю боярские жены, сопровождавшие Елену, расплели ей волосы, причесали, надели на нее кику и обрызгали ее хмелем. Священник Фома прочел молитвы, благословил невесту, и Елена отправилась в костел, где ее ожидал Александр. Фома, неся крест, шел с ней рядом. Ксендз с распятием встретил Елену перед собором. Все вместе они вошли внутрь, и Елена заняла место около Александра. Епископ совершил католический свадебный обряд. Митрополит Макарий присутствовал, но участия в службе — так распорядился Александр — не принимал. Фома, однако, читал молитвы по-славянски, а княгиня Мария Ряполовская, согласно русской традиции, подняла над головой Елены свадебный венец. Епископ и сам Александр гневно высказали князю Ряполовскому недовольство таким нарушением католического обряда. Ряполовский попытался остановить Фому и Марию, но они упрямо продолжали делать то, что считали своим долгом. После свадьбы Александр отправился в свою часть дворца, а Елена — в свою. Затем Александр пригласил русских бояр на банкет. В заключение отчета Ивану III бояре отметили, что Елена на свадебной церемонии была в русском наряде, и добавили с явным удовлетворением: «И сегодня, на четвертый день после свадьбы, великая княгиня все еще носит собственное платье и кику».