Иоанн, получив записку Шестакова, послал в Литву Ивана Мамонова с приказом от себя и от жены к Елене, чтоб пострадала до крови и до смерти, а веры греческого закона не оставляла. Решившись начать войну, Иоанн хотел узнать средства противника и потому наказал Мамонову: «Пытать, был ли у Александра Стефанов посол и заключен ли мир между Молдавиею и Литвою. Польский и венгерский короли в мире ли с Стефаном? Турский и перекопский мирны ли с польским, литовским и молдавским?» Об отношениях Литвы к Молдавии сам Александр уведомил тестя чрез посла своего Станислава Глебовича, который объявил о мире между Стефаном и Александром и от имени последнего приглашал Иоанна помочь Молдавии против турок. «Сам можешь разуметь, — велел сказать Александр, — что Стефана-воеводы панство есть ворота всех христианских земель нашего острова; не дай бог, если турки им овладеют!» Глебович жаловался, что наместник козельский захватил села карачевские и хотимльские, что бояре, живущие на новгородских границах, отняли торопецкие земли; относительно титула Иоаннова Александр велел объявить следующее: «В докончальной записи вписаны были все земли и места и волости литовские, кроме замка Киева и пригородов, теперь впиши Киев либо особый лист нам дай на него, тогда и будем тебя писать, как написано в договоре». Иоанн велел отвечать, что подаст помощь Стефану, когда тот сам пришлет просить ее, что земли, отнятые наместником козельским, исстари принадлежат к его городу, что Александр выступил из договора, принуждая Елену принять латинство; относительно Киева и титула ответ был такой: «Князь бы великий сам положил на своем разуме, гораздо ли так к нам приказывает? Мимо нашего с ним договора и крестного целования не хочет нам править по докончанию да такие нелепицы к нам и приказывает мимо дела».
Скоро после этого Менгли-Гирей прислал в Москву условия, на которых хотел помириться с Литвою: он требовал ежегодной дани с 13 литовских городов, между которыми были Киев, Канев, Черкассы, Путивль. «По тем городкам, — писал хан, — дараги были и ясаки брали». С этими условиями Иоанн отправил в Литву опять Мамонова, который должен был требовать, чтоб Александр дал ответ, пока Менгли-Гиреевы послы в Москве; Елене Мамонов должен был сказать упрек, зачем она таится от отца касательно принуждении к перемене веры, и новое увещание быть твердою в православии. Александр отвечал с Мамоновым: «Пусть великий князь сам посмотрит и совет нам свой даст о Киеве и других городах наших — пристойные ли то речи? Менгли-Гирей хочет от нас того, чего его предки от наших предков никогда не хотели. Поговорим с папами Радою и пришлем с ответом своего посла, а великий князь до тех пор пусть Менгли-Гиреева посла позадержит». Иоанн послал сказать Менгли-Гирею: «Мы по твоему слову посла своего посылали к великому князю Александру и то ему сказали, какого ты с ним мира хочешь. Он нам велел сказать с нашим послом, что его люди при отце его и деде к вашей Орде даньщиками никогда не бывали, и обещал нам для этих дел выслать своих послов, приказавши, чтоб мы от себя твоих послов не отпускали до тех пор, пока будут у нас его послы, и мы затем твоих послов у себя и держали, ждали к себе от него послов, но он к нам послов не присылывал. И если князь великий Александр послов своих к нам не прислал, так он с тобою мира не хочет; с нашими недругами, с Ахматовыми детьми, ссылается, наводит их на нас, а которые послы Ахматовых детей теперь у него, и он тех послов в Орду отпускает да и своих послов туда шлет и в своем слове не стоит, что приказывал нам, будто мира с тобою хочет. И если он с тобою, нашим братом, мира не хочет, то и я с ним мира не хочу для тебя, хочу с тобою, своим братом, по своей правде на него быть заодно, и если пришлет к тебе князь великий Александр за миром, то ты бы с ним не мирился без нашего ведома; как даст бог нам с литовским свое дело делать и на него наступить, то мы с тобою сошлемся». Послу было наказано: «Беречь накрепко, чтоб Менгли-Гирей с великим князем литовским не мирился, не канчивал. Если Менгли-Гирей спросит, в мире ли великий князь с литовским или нет, то послу отвечать: „Александр хотел прислать послов с ответом насчет мира с тобою и не прислал; с тех пор государь наш для тебя с ним в размирьи“. Если хан спросит: „В чем у них размирье?“ — отвечать: „Приехал князь Бельский с вотчиною, и великий князь его принял“.
Действительно, прислал в Москву князь Семен Иванович Бельский бить челом великому князю, чтоб пожаловал, принял его в службу и с отчиною: терпят они в Литве большую нужду за греческий закон; великий князь Александр посылал к своей великой княгине Елене отметника православной вере, Иосифа, владыку смоленского, да епископа своего виленского и монахов бернардинских, чтоб приступила к римскому закону; посылал и к князьям русским, и к виленским мещанам, и ко всей Руси, которая держит греческий закон, принуждает ее приступить к римскому закону, а смоленскому владыке великий князь обещал за то Киевскую митрополию. Иоанн принял Бельского и послал сказать Александру: «Князь Бельский бил челом в службу; и хотя в мирном договоре написано, что князей с вотчинами не принимать, но так как от тебя такого притеснения в вере и прежде от твоих предков такой нужды не бывало, то мы теперь князя Семена приняли в службу с отчиною». Бельский также послал Александру грамоту, в которой слагал с себя присягу по причине принуждения к перемене веры. За Бельским перешли с богатыми волостями князья, до сих пор бывшие заклятыми врагами великого князя московского: князь Василий Иванович, внук Шемяки, и сын приятеля Шемякина, Ивана Андреевича Можайского, князь Семен Иванович; князь Семен поддался с Черниговом, Стародубом, Гомелем, Любичем; Шемячич — с Рыльском и Новгородом Северским; поддались другие князья, менее значительные, — Мосальские, Хотетовские, все по причине гонения за веру. Иоанн послал объявить Александру, что принял в службу Можайского с Шемячичем, и в то же время послал складную грамоту, или объявление войны.
Московские войска выступили в поле под начальством хана Магмет-Аминя и воеводы Якова Захарьевича Кошкина, заняли города: Мценск, Серпейск, Мосальск, Брянск, Путивль; князья северские — Можайский и Шемячич — были приведены к присяге; другая рать, под начальством боярина Юрия Захарьевича Кошкина, взяла Дорогобуж. Вслед за ним великий князь отправил тверскую рать под начальством князя Даниила Щени, который должен был начальствовать большим полком, а боярин Юрий — сторожевым; Юрий обиделся и писал в Москву, что ему в сторожевом полку быть нельзя: «То мне стеречь князя Данила!» Великий князь велел отвечать ему: «Гораздо ль так делаешь? Говоришь, что тебе непригоже стеречь князя Данила: ты будешь стеречь не его, но меня и моего дела; каковы воеводы в большом полку, таковы и в сторожевом: так не позор это для тебя». Юрий успокоился. Между тем литовское войско под начальством гетмана князя Константина Острожского приближалось к Дорогобужу и 14 июля 1500 года, в годовщину Шелонской битвы, встретилось с московским на Митькове поле, на речке Ведроше. Благодаря тайной засаде, решившей дело, московские воеводы одержали совершенную победу: гетман князь Острожский и другие литовские воеводы попались в плен. 17 июля получил великий князь весть о победе, и была радость большая в Москве, говорят летописцы. Победителей великий князь послал спросить о здоровье; пленники привезены в Москву и отсюда разосланы по городам: князь Константин Острожский отправлен в Вологду в оковах; держали его крепко, но поили и кормили довольно; прочим князьям и панам давали по полуденьге на день, а Константину — по четыре алтына; скоро, впрочем, он присягнул служить великому князю московскому, получил свободу и земли.