Осенью 1430 г. московский, тверской и рязанский князья были вызваны в Вильну. Витовт готовился одеть на себя королевскую корону. Однако коронация не состоялась, а вскоре после отъезда гостей Витовт умер. Год спустя в Москве скончался митрополит Фотий. В Литве к власти пришел свояк князя Юрия Свидригайло. Василий II не мог более противопоставить врагам союз с Литвой.

После смерти Витовта, повествует летопись, Юрий «разверже» мир с Василием II и отослал в Москву текст договора 1428 г. В подлиннике была тогда же сделана помета: «А ею грамоту князю великому прислал /со/ складною (грамотой. — Р.С.) вместе князь Юрьи, к Орде ида». Складную грамоту посылали при объявлении войны. Но не это вызвало переполох в Москве. Бояре были смущены тем, что удельный князь в соответствии с первым докончанием 1425 г. решил отправиться в Орду, чтобы судиться с племянником из-за ярлыка на великое княжество. Исход суда зависел от того, кто первый прибудет к ханскому двору и успеет доказать свою преданность Орде. В таких условиях правитель И. Д. Всеволожский убедил Василия II ехать в Орду и лично возглавил его скиту. Ко времени путешествия государю исполнилось пятнадцать лет, и он достиг совершеннолетия.

Отчет о переговорах в Орде был составлен московской канцелярией при участии правителя И. Д. Всеволожского. Отчет почти целиком состоял из пересказа речей Всеволожского, похвал по поводу его удивительных дипломатических успехов. Однако при ближайшем рассмотрении эти успехи выглядели как полнейшее поражение.

Отправившись в Орду для решения спора о владимирской короне, русские князья поставили себя в унизительное и трудное положение. Улу-Мухаммед проявил пренебрежение к князьям из русского улуса, продержав их у себя почти год. Василий II попал в юрту к московскому даруге Минбулату. Князя Юрия забрал на зиму в Крым мурза Тегин. Летом 1432 г. князья были приглашены в ставку. Василий II попросил себе ярлык на великое княжение, но Юрий опроверг его доводы «летописцы старыми списки и духовную отца своего великого князя Дмитрия». В духовной значилось, что по смерти Василия I трон переходит к следующему по старшинству брату, т. е. Юрию. В диспут вмешался И. Д. Всеволожский. Он заявил, что Юрий желает получить великое княжение «по мертвой грамоте отца своего, а не по твоему жалованию водного царя». Летописец старался преподнести эти слова как триумф московской дипломатии. Но в действительности речь правителя свидетельствовала о полной капитуляции.

Правитель постарался убедить властителя Орды, что его московский государь ищет великого княжения из ханской руки — «твоего улуса, по твоему цареву жалованию и твоим девтерем и ярлыком». Согласно московской версии, демарш Всеволожского привел к немедленному успеху. Летописи независимого происхождения свидетельствуют об обратном. Миссия правителя закончилась провалом. Орда по традиции делала ставку на сильнейшего из русских князей. Но Улу-Мухаммед не был уверен, что малолетний племянник одолеет дядю. По Новгородской летописи, «выидоша князи рустии из Орды без великаго княжениа». О том же говорит и псковский летописец: Василий II с дядей и все бояре с ними выехали из Орды «добры и здравы, а княжения не взят не един». Лишившись на год государя, московский правящий круг должен был признать, что решение о поездке в Орду явилось серьезной ошибкой. Итоги миссии Всеволожского вызвали глубокое разочарование. Орда направила на Русь вслед за князьями посла Мансыр-Улана. Он посадил Василия II на владимирский трон, но одновременно стал добиваться от него выполнения финансовых обязательств.