К этим неудовольствиям присоединились пререкания о титуле; так как Александр в посольских грамотах не хотел писать тестя государем всея Руси. А Иоанн не исполнял просьбы зятя помирить его с Менгли-Гиреем Крымским и Стефаном Молдавским. На границах продолжались враждебные столкновения между жителями обеих сторон, продолжались переходы людей из литовского подданства в московское и захваты литовских владений. Александр, очевидно, в государственной политике был еще ниже своего отца и дал волю проискам католического духовенства для разных притеснений православной церкви. По крайней мере один из князей Вельских, остававшихся в литовском подданстве, Семен Иванович (брат помянутого выше Федора Вельского), в 1499 году перешел в московскую службу, ссылаясь прямо на притеснения православию и понуждения к перемене веры. Его примеру последовали потомки известных московских перебежчиков времен Темного, именно внук Шемяки Василий и сын Ивана Андреевича Можайского Семен. Они поддались государю Московскому с городами Черниговом, Гомелем, Любичем, Рыльском, Новгород-Северским. Таким образом, большая часть Черниговско-Северской земли воссоединялась с Восточной Русью. Подобное приобретение, конечно, не могло обойтись без войны. Иоанн послал воевод, которые заняли ближайшие северские города, Мценск, Серпейск, Мосальск, Брянск, Путивль и также смоленский город Дорогобуж. И уже после открытия военных действий он послал зятю объявление войны. Литовско-русское войско, предводимое своим гетманом, князем Константином Острожским, на берегах Ведроши, около Дорогобужа, встретилось с большой московской ратью, в которой главным воеводой был князь Даниил Щеня. Битва произошла 14 июля 1499 года и окончилась полным поражением литовцев. Сам Острожский и некоторые другие их предводители попали в плен. Московские войска имели еще несколько успешных дел в разных местах. Но попытка взять Смоленск не удалась. Затем война между Москвой и Литвой тянулась еще четыре года, но без решительных действий с той или другой стороны.
В этой войне союзником Иоанна были молдавский господарь Стефан и крымский хан Менгли-Гирей, а сторону Литвы держали незначительные золотоордынские ханы, сыновья Ахмата. Зато Александру удалось приобрести важного и деятельного союзника против Москвы в лице ливонского магистра.
С тех пор как Псков стал в подчиненные отношения к Москве, последняя неизбежно должна была присылать свои войска для его обороны от ливонских немцев, с которыми у псковичей никогда не было прочного мира. В 1492 году, при истечении заключенного между ними десятилетнего перемирия, Иван III воздвиг каменную крепость на пограничной реке Нарове, против эстонского города Ругодина или Нарвы. Эта крепость, снабженная массивными стенами, высокими башнями и названная по имени своего основателя Ивангородом, должна была в случае войны служить опорным пунктом и против немцев, и против шведов. В следующем году немецкие послы приехали в Новгород и с наместниками великого князя заключили договор о продлении перемирия еще на десять лет. Но оно было нарушено гораздо ранее срока.