В 1430 же году Василий ездил к Витовту на пир в Троки по случаю предполагавшейся его коронации. Туда же, помимо московского князя и митрополита Фотия, приехали князья тверской, рязанский, представители ордынцев, послы Византии, находившийся в изгнании Валашский господарь, король Польши Ягайло, великий магистр Прусский, ландмаршал Ливонский и некоторые другие, более мелкие правители. Но коронация расстроилась из-за активного противодействия польских магнатов, и Витовт так и остался без короны. Эта неудача, по-видимому, настолько сильно подточила его силы, что в том же году он скончался, а литовским князем стал другой Гедиминович, брат Ягайло, — Свидригайло. Со смертью Витовта ушла в небытие целая эпоха истории Литвы и русско-литовских взаимоотношений. В следующем году, 2 июля, скончался и митрополит Фотий. Уход с политической арены таких крупных фигур развязал руки Юрию, решившему, что теперь он может добиться успеха в Орде. Оба князя начали приготовления к отъезду.
В августе, после длительных молебнов и раздачи милостыни по монастырям, отобедав на лугу против Симонова монастыря, Василий II поехал в Орду ко двору хана Улу-Мухаммеда в сопровождении хитрого и ловкого боярина Ивана Дмитриевича Всеволожского, потомка смоленских удельных князей, служившего по Москве. Чуть позже, в середине сентября того же 1431 года, поспешил в Орду и Юрий, вернувший великому князю договор 1428 года со «складною вместе». Оба претендента отправились к хану с богатыми дарами, без которых, как водится, ни одно дело не решалось. В Орде у Василия нашелся влиятельный покровитель — некий вельможа Минбулат, который оказывал московскому князю «честь великую». Юрия же он держал «в истоме», то есть попросту в плену. Но и за Юрия вступился покровитель — знатный ордынец Тегиня из известного рода Ширинов. Он «силою» забрал галицкого князя от Минбулата и вместе с ним отправился в Крым, где они и провели всю зиму. Тегиня обещал Юрию поддержку, но и москвичи не сидели сложа руки. Боярин Всеволожский провел в пользу Василия большую «работу» среди ордынской аристократии. Особым влиянием здесь пользовался князь Айдар, которому Всеволожский сумел внушить мысль, что в случае передачи ярлыка Юрию возрастет и влияние при дворе Тегини, грозившее Айдару и другим князьям серьезными осложнениями («а вас что тогда будет?»). Кроме того, Юрий был «побратимом» Свидригайло, с которым у ордынских вельмож сложились сложные отношения.
Власть хана в Орде все более и более попадала в зависимость от влияния тех или иных усилившихся вельмож, это не было уже прежнее единодержавие, поэтому голоса Айдара и других ордынцев достигли цели. Улу-Мухаммед решил передать стол Василию и приказал, как только появится Тегиня, убить его. Весной 1432 года Тегиня и Юрий приехали из Крыма. Они были предупреждены верными людьми о решении хана, но Юрий решил идти до конца. Разгорелся спор князей, каждый предъявлял свои аргументы, но исход дела решил все тот же Всеволожский. Он выступил перед ханом с речью, в которой отметил, что Юрий хочет стать князем не по воле хана, а по «мертвой грамоте отца своего», Василий же, напротив, добивается, прежде всего, ханского ярлыка, так как признает себя вассалом Орды, а Русь ее улусом. К тому же хитрый царедворец как бы невзначай заметил, что Василий уже который год сидит на престоле, исправно неся службу «тебе, своему государю». Эти слова решили исход разбирательства: Улу-Мухаммед отдал ярлык Василию, но, опасаясь Тегини, присоединил к владениям Юрия и выморочный Дмитров. Юрий должен был вести коня под Василием в знак покорности, но великодушный великий князь освободил своего дядю от такого унижения. По возвращении на Русь Василий был поставлен в Москве на великокняжеский стол ордынским послом царевичем Мансыр-уланом 5 октября 1432 года. Юрий ушел к себе в Галич, Дмитров Василий скоро присоединил к своим владениям. Но успокоение на Руси опять оказалось лишь временным.
Дальнейшая борьба за Москву разгорелась по инициативе все того же боярина Всеволожского.