Иван вел борьбу за воссоединение Руси, за создание единого Русского государства с включением в его состав всех старинных русских земель, захваченных некогда Литвой и Польшей, — Смоленской, Чернигово-Северской, Киевской, Полоцкой, Пинской, Берестейской, Галицкой и Волынской. Он воевал за Русь в границах киевских времен: от Волги до Галича и Черной Руси, от Мурома до Переяславля, Канева, Черкас и Олешья. И поэтому в 1493 г. посол его, дворянин Загряжский, читая грамоту Ивана Александру, поразил литовцев новым титулом московского князя: в грамоте Иван именовал себя «государем всея Руси», а не «великим князем», как ранее. Иван заявлял, что его «отчина» — «Киев и Волынская земля, и Полоцк и Витебск и иные городы русские многы», ибо «…вся Русская земля, Божию волею, из старины, от наших прародителей, наша отчина».
Эти притязания Ивана были подкреплены силой оружия; поэтому вскоре, в 1494 г., литовские послы заключили мир с Иваном. По мирному договору, к Москве отходили Вязьма, Серпейск, Козельск, Любутск и часть Мезецких княжеств; кроме того, Александр признал Новосильское, Одоевское, Перемышльское, Воротынское и Белевское княжества «тянущими» к Москве. Вскоре состоялось и обручение Александра с дочерью Ивана Еленой. Иван при этом требовал, чтобы Елену не принуждали принимать католичество, построили бы ей православную церковь, а ей самой при отъезде в Литву приказал помогать русским, православным, и ходатайствовать за них перед Александром. Для Александра условия брака были позором. Он даже побоялся признаться римскому папе об условиях женитьбы на Елене. Паны, конечно, встретили этот брак враждебно. Елена жаловалась отцу, что Александр не выполняет условий договора. Действительно, Александр содействовал насильственному внедрению католичества в русских землях. Поьдячий Шестаков писал в 1499 г. из Литвы в Москву: «Между Латинами и нашим христианством стала смута великая… Все наше православное христианство хотят окрестить». Мстя за мир 1494 г., Александр натравливал на Ивана татар, шведов. Правда, его попытки не увенчались успехом. Не «стерпя насилия», русские князья из Литвы все чаще и чаще отъезжали «на Москву».
Иван спешно готовился к новой войне. Собирали отряды пищальников, псковичи составляли ополчение: бобыли шли в пехоту, крестьяне с «десяти сох» давали коня, с «сорока рублев» горожане ставили «коня и воина в доспехах». Собирались «даточные люди» и по другим русским землям, сходились отряды князей и бояр. Решено было ударить на Литву по трем направлениям: на Оку, Сейм, Десну, Сож, на Западную Двину и на верховья Днепра. В мае 1500 г. Иван послал Александру гонца со «складной грамотой», т. е. снимал с себя присягу 1494 г., но «разметной грамоты» он не послал — Иван не воевал с Литвой за литовские земли, а возвращал себе русские, что, по его мнению, его право, добываемое не войной.
В мае же русские войска двинулись в поход. Один за другим освобождались старинные русские города — Мценск, Брянск, Трубчевск, Гомель, Чернигов, Любеч, Новгород-Северский, Стародуб, Путивль, Рыльск, Радогощь. В это же время псковские рати освободили Торопец.
Главный удар московское войско наносило в направлении на Дорогобуж и Смоленск. Во главе «большого полка», двигавшегося на Смоленск, стоял воевода московский боярин Юрий Захарьевич. Позднее его сменил в этой роли Даниил Щеня. Юрий Захарьевич вздумал было обидеться, но времена, когда можно было «местничать» в походе, прошли, и грозный окрик Ивана заставил строптивого боярина смиренно возглавить «сторожевой полк», для того чтобы стеречь «государское дело» и отличиться в бою, «малыми людьми» взяв Дорогобуж.
Навстречу прорвавшемуся далеко на запад Юрию Захарьевичу шел с воинством литовским гетман Константин Острожский. Но и к Юрию Захарьевичу вскоре подошли «другие большие воеводы». На берегу реки Ведроши, близ Дорогобужа, на Митьковом поле, литовские рати поджидало русское воинство. Русские передовые отряда перешли реку, инсценировали бегство, литовцы бросились через Ведрошь и тогда русские обрушили свой удар на них. Началась страшная сеча. Русские отряды прорвались вперед, уничтожили мост, наведенный Острожским через реку, а Даниил Щеня бросил в бой «засадный полк». Битва 14 июля 1500 г. закончилась полным разгромом войск Александра. Гетман, князь Константин Острожский, был взят в плен и отвезен в Вологду. 17 июля, день получения Иваном вести о победе при реке Ведроше, был объявлен праздничным днем в Москве.
Русские войска двинулись дальше, громя везде литовцев. Русские бились под Мстиславлем, осаждали Смоленск. Александр прибег тогда к помощи венгерского посла, и тому удалось уговорить Ивана заключить перемирие на шесть лет — от 25 марта 1503 г. до 25 марта 1509 г.