После присоединения Новгорода Московия превратилась в балтийскую державу, и перед Иваном III встали новые проблемы. Цели его балтийской политики сводились к трем пунктам: разрушить торговую монополию Ганзейского союза, защитить Новгород и Псков от нападений ливанских рыцарей и обезопасить от посягательств шведов выход через Неву в Финский залив.

В 1492 году Иван приказал построить крепость на восточном берегу Нарвы, недалеко от ее устья и напротив немецкого города Нарва. Крепость, получившая название Ивангород, скоро приобрела большое экономическое значение как новый порт для торговых судов, курсирующих в Балтийском море.

В июле 1493 года в Москву прибыл датский посол и была подготовлена почва для соглашения Дании и Москвы. Осенью в Данию отправилось ответное посольство, и 8 ноября в Дании был подписан союзный договор между королем Хансом Датским и Иваном III. Два правителя взяли на себя обязательства поддерживать друг друга «насколько возможно». Отдельным пунктом соглашения стала договоренность о совместной акции против правителя Швеции Стена Стуре — узурпатора с точки зрения короля Ханса, заявлявшего собственные права на корону Швеции. Для Ивана III союз с Данией был вдвойне ценен: он позволил ему смелее вести себя с Ганзой и давал возможность ослабить шведский контроль над Финляндией. Год спустя Иван III закрыл Ганзейский двор в Новгороде, а в 1495–1496 годах русские приняли участие в войне датчан против Швеции. Русская армия воевала в Финляндии и даже доходила до Ботнического залива. Союзники выиграли войну, Ханс получил корону Швеции (1497).

Тем временем возникли новые противоречия между Московией и Литвой. Брак Елены и Александра, вместо того чтобы сделать отношения между Иваном III и Александром более сердечными, посеял семена нового конфликта. Иван III, никогда не позволявший личным чувствам мешать политике, был готов пожертвовать семейным счастьем дочери ради русских национальных и религиозных интересов. С другой стороны, папа и римско-католическое духовенство в Литве оказывали давление на Александра, требуя от него либо убедить супругу принять католичество, либо развестись с ней.

Вскоре литовское правительство предприняло новую попытку подчинить западнорусскую церковь папе. В 1497 году во время набега крымских татар погиб митрополит Киевский Макарий. На его местд великий князь Александр назначил епископа Смоленского Иосифа. Новый митрополит принадлежал к аристократическому западнорусскому роду и приходился родственником Яну Сапеге, секретарю великого князя Александра. Сапега, ранее исповедовавший православие, в 1492 году перешел в лоно католической церкви. Иосиф выступал за объединение западнорусской церкви с Римом. В 1500 году он направил папе письмо, объявив о своем желании принять Флорентийскую унию. Но еще до этого события православные Литвы жаловались Ивану III, что их религиозные права ущемляются.

В 1499 году, понимая, что новое столкновение с Литвой неотвратимо, Иван III обсудил с ханом Менгли-Гиреем вопрос о разделении сфер влияния Московии и Крыма в украинских землях Великого княжества Литовского. Менгли-Гирей согласился отдать под юрисдикцию Ивана III Киев и Черкассы.

В апреле 1500 года на сторону Ивана перешли два русских князя из Черниговско-Северской земли — Семен Иванович Можайский и Василий Иванович Шемячич. Они оба были потомками старых врагов Василия II, и их драматический переход из-под литовского сюзеренитета к московскому был весьма важен для Ивана.

В мае 1500 года Иван III отправил в Вильно декларацию об объявлении войны, основываясь на том, что литовское правительство не соблюдает условий договора от 1494 года и требует, чтобы Елена изменила веру. К этому моменту Литва имела союзные договоры с Ливонией и Золотой Ордой. Кроме того, в 1501 году Александр унаследовал польскую корону после смерти брата Яна-Альбрехта, и династическое единство Польши с Литвой было восстановлено. Союзниками Московии были Крым и Дания. Но когда начались боевые действия, внимание Менгли-Гирея переключилось на Золотую Орду, которую он и сокрушил в 1502 году; таким образом, Крым не оказал Ивану III значительной поддержки. Король Ханс Датский вообще ничем не помог, потому что в 1501 году восстала Швеция и он был вынужден послать туда дополнительные войска.

В результате Московии пришлось воевать с Литвой и Ливонией в одиночку. Война началась 14 июля 1500 года. В первый ее год московиты нанесли сокрушительное поражение литовской армии на берегах реки Ведроши. Московской армией командовали боярин Юрий Захарьевич Кошкин и князь Данила Щеня; литовцами — западнорусский аристократ, князь Константин Иванович Острожский. В конце лета 1500 года московская армия заняла большую часть черниговско-северской территории. В то же время попытки Москвы взять штурмом Смоленск в октябре 1502 года результата не принесли — из-за слабости московской артиллерии.

Успешная оборона Смоленска позволила литовскому правительству начать переговоры о мире, сохранив при этом достоинство. Папа Александр VI вызвался быть посредником, рассчитывая включить и Литву и Москву в антитурецкую коалицию, которую он пытался организовать. Иван III, однако, предпочел вести переговоры непосредственно с Александром. Литовские и ливонские послы прибыли в Москву 4 марта 1503 года. С ливонскими послами Иван дело иметь отказался и направил их к своему наместнику в Новгороде. Переговоры же с литовцами начались немедленно, но скоро стало ясно, что ни одна из сторон не готова идти на уступки достаточно значительные, чтобы обеспечить устойчивый мир. Поэтому 2 апреля 1503 года вместо мира было заключено перемирие сроком на шесть лет. Согласно этому документу, все пограничные районы Великого княжества Литовского, захваченные московскими войсками в течение войны (и удерживаемые ими на момент переговоров), на время перемирия оставались под властью Ивана III.

Так, в вассальной зависимости от Москвы оказались Дорогобуж и Белая в Смоленской земле, Брянск, Мценск, Любутск и несколько других верхних городов, большая часть Черниговско-Северской земли (бассейны рек Десна, Сож и Сейм), а также город Любеч на Днепре, севернее Киева. Москва, таким образом, получила контроль над сухопутным путем в районе Среднего Днепра, что заметно облегчало доступ в Крым московским купцам и дипломатическим представителям.

Вскоре после заключения московско-литовского перемирия в Новгороде было подписано перемирие с Ливонским орденом. Оно не повлекло за собой никаких территориальных перемен, но содержало обязательство со стороны епископа Дерпта по старому обычаю ежегодно выплачивать символическую дань Ивану III как сюзерену Пскова.