Тем временем изменения политического характера произошли и в Орде. Здесь один из сыновей Тохтамыша — Сеид-Ахмед изгнал Улу-Мухаммеда, и тот с небольшим отрядом пришел в район города Белева на русской границе, поставил там городок и решил зимовать (1437 г.). Это, конечно, не могло понравиться Василию II. Московский князь направил против бывшего хана рать во главе с Дмитрием Шемякой и Дмитрием Красным. Еще недавно Василий ездил к Улу-Мухаммеду на поклон, и вот теперь сам хан принужден был искать спасения в русских землях. По пути к Белеву братья Юрьевичи вели себя как заправские разбойники: «все пограбиша у своего же православного христьянства, и мучаху людей из добытка, и животину бьюще, назад к себе отсылаху, все грабяху и неподобная и скверная деяху». Первоначально успех сопутствовал московскому войску, ордынцы были разбиты и отброшены в город. Хан отправил к Юрьевичам посольство, предлагая своего сына в заложники и обещая (в случае занятия ханского престола) всяческую помощь Москве и отказ от русской дани. Бывший властитель Золотой Орды, таким образом, почти оказался на положении пленника. Воеводы Василия отвергли все предложения хана и решили добить ордынцев. 5 декабря 1437 года состоялось новое сражение, в котором, благодаря измене мценского воеводы Григория Протасьева, Улу-Мухаммеду удалось разбить русские полки. Впоследствии Протасьев был «поиман» и по приказу Василия ослеплен. Из-под Белева Улу-Мухаммед отошел на Волгу, где формировалось Казанское ханство. Бывший хан Золотой Орды стал правителем этого государства.
Ободренный успехом «белевщины», 3 июля 1439 года Улу-Мухаммед внезапно с большими силами подступил к стенам Москвы. Действия Василия II не отличались оригинальностью. Не успев, разумеется, подготовиться к отпору врага, он уехал из Москвы за Волгу. Оборону города возглавил воевода Юрий Патрикеевич. Ордынцы стояли под Москвой 10 дней, взять город им не удалось, но они сожгли посад и захватили большой полон. На обратном пути хан сжег Коломну «и людей множество плени, а иных изсекл». После отхода Улу-Мухаммеда Василий отправил в Москву наместником Дмитрия Красного, а сам прожил всю зиму в Переяславле и Ростове, «бе бо посады пождьжены от татар, и люди посечены, и смрад велик от них». Во время осады Москвы Шемяка не послал свои полки на помощь великому князю.
Неприязненные отношения между кузенами вылились вскоре в очередной конфликт. Осенью 1441 года Василий неожиданно пошел на Углич. Для Шемяки это было полной неожиданностью, и он мог попасть в плен, если бы не предупреждение дьяка Кулудара Ирежского. Впоследствии дьяк был лишен своего звания и наказан по распоряжению Василия кнутом. Князь Дмитрий бежал в Бежецкий Верх, откуда послал в Новгород просить новгородцев принять его. Ответ горожан был уклончив: «Хошь, княже, и ты к нам поеди; а не всхошь, ино как тобе любо». Шемяка, видимо, решил, что пока с новгородцами связываться не стоит, и, собрав рать, двинулся на Василия. К Юрьевичу присоединился и князь Александр Чарторыйский, потомок Гедимина, недавно убивший вместе с братом Иваном великого литовского князя Сигизмунда.
Под Троицким монастырем врагов помирил игумен Зиновий. Василий и Дмитрий составили договор, по которому в удел Шемяки входили Галич, Руза, Вышгород, Углич и Ржева.
Ордынцы продолжали совершать набеги на русские земли. Зимой 1443 года царевич Мустафа пошел в Рязанскую землю, пожег села и забрал большой полон. Потом он продавал пленников самим же рязанцам. Зима выдалась лютой, стояли трескучие морозы, и Мустафа вновь вернулся в Рязань, но теперь уже не в качестве захватчика, а на зимовку. Узнав об этом, великий князь послал на Мустафу войско под руководством воевод князей Василия Оболенского и Андрея Фёдоровича Голтяева. К ним присоединилась и мордва на лыжах. Бой произошел на реке Листани. Ордынцы не могли стрелять из обледеневших луков, но сражались отчаянно, не желая сдаваться в плен. Татарское войско было разбито, среди погибших был и Мустафа.
Казанский хан Улу-Мухаммед также продолжал беспокоить русские пределы. Зимой 1444 года он вошел в Нижний Новгород, а затем захватил и Муром. В Нижнем небольшая кучка жителей заперлась в крепости, построенной еще князем Дмитрием Константиновичем, и выдержала ордынскую осаду. Василию II удалось выбить татар из Мурома, но весной в Москву пришло известие, что Улу-Мухаммед послал на великого князя своих сыновей Мамутяка и Якуба. Собрав войско, Василий выступил в поход и вскоре был в Юрьеве. Сюда прибежали и нижегородские воеводы. Доведенные голодом до крайности и не выдержав долгой осады, они ночью подожгли крепость и бежали. Поход Василия был плохо организован. Шемяка вообще не явился на помощь. 6 июля 1445 года русское войско вышло к реке Каменке и остановилось у Спасо-Евфимьева монастыря недалеко от Суздаля. Ранним утром 7 июля Василий получил известие, что ордынцы перешли реку Нерль. Битва у монастыря оказалась трагедией для русских. Великий московский князь попал в плен.