После этой победы Улу-Махмет пошел степью мимо русских границ, переправился через Волгу и засел в опустелой от русских набегов Казани, где поставил себе деревянный город на новом месте, и в июле 1439 года явился нечаянно под Москвою. Великий князь не успел собраться с силами и уехал за Волгу, оставив защищать Москву воеводу своего, князя Юрия Патрикеевича; хан стоял 10 дней под городом, взять его не мог, но наделал много зла Русской земле, на возвратном пути сжег Коломну и погубил множество людей. В 1444 году султан Мустафа пришел на Рязань со множеством татар, повоевал волости и села рязанские и остановился в степи для продажи пленников, которых выкупали рязанцы. Когда пленные были все выкуплены, Мустафа пришел опять в Рязань, на этот раз уже с миром; хотелось ему зимовать в городе, потому что в степи не было никакой возможности оставаться: осенью вся степь погорела пожаром, а зима была лютая, с большими снегами и сильными вьюгами; от бескормицы лошади у татар перемерли. Когда в Москве узнали об этом, то великий князь отправил на Мустафу двоих воевод своих – князя Василия Оболенского и Андрея Голтяева – с двором своим да мордву на лыжах. Московские воеводы нашли Мустафу под Переяславлем на речке Листани, потому что рязанцы выслали его из своего города. Несчастные татары, полузамерзшие, бесконные, не могшие владеть луками по причине сильного вихря, должны были выдержать нападение с трех сторон: от воевод московских, от мордвы и от казаков рязанских, которые упоминаются тут в первый раз. Несмотря на беспомощное состояние свое, татары резались крепко, по выражению летописца, живыми в руки не давались и были сломлены только превосходным числом неприятелей, причем сам Муста-фа был убит. Другие татары в том же году отплатили за Мустафу нападением и на Рязанскую украйну, и на землю Мордовскую; а в 1445 году хан Улу-Махмет засел в старом Нижнем Новгороде и оттуда пришел к Мурому. Великий князь вышел против него со всеми своими силами, с князьями – Шемякою, обоими Андреевичами и Василием Ярославичем; хан испугался и убежал назад в Нижний Новгород, только передовым полкам великокняжеским удалось побить татар под Муромом, Гороховцом и в других местах.
Но иначе кончилось дело при второй встрече Василия с татарами Улу-Махметовыми. Весною того же года пришла в Москву весть, что двое сыновей Улу-Махметовых опять появились в русских границах, и великий князь, заговевшись на Петров пост, вышел против них. В Юрьев прискакали к нему нижегородские воеводы – князь Федор Долголядов и Юшка Драница – с вестию, «что они выбежали ночью из города, зажегши его, потому что не могли долее переносить голода: что было хлебного запасу, все переели». Тогда великий князь, проведши Петров день в Юрьеве, пошел к Суздалю и стал на реке Каменке, куда пришли к нему двоюродные братья Андреевичи и Василий Ярославич. 6 июля московское войско переполошилось, надели доспехи, подняли знамена и выступили в поле, но неприятель не показывался, и великий князь, возвратившись в стан, сел ужинать с князьями и боярами; долго пили ночью, встали на другой день уже после солнечного восхода, и Василий, отслушав заутреню, хотел было опять лечь спать, как пришла весть, что татары переправляются чрез реку Нерль. Великий князь тотчас же послал с этою вестию по всем станам, сам надел доспехи, поднял знамена и выступил в поле, но войска было у него мало, всего тысячи с полторы, потому что полки союзных князей не успели собраться, не успели прийти и союзные татары, не пришел и Шемяка, несмотря на то что к нему много раз посылали. Подле Евфимиева монастыря, по левую сторону, сошлись русские полки с татарами, и в первой стычке рать великокняжеская обратила в бегство татар; но когда стала гнаться за ними в беспорядке, то неприятель обратился и нанес русским совершенное поражение. Великий князь отбивался храбро, получил множество ран и был наконец взят в плен вместе с двоюродным братом Михаилом Андреевичем; князь Иван Андреевич можайский был также ранен и сбит с коня, но успел пересесть на другого и спасся бегством. Победители рассыпались по окрестностям для грабежа, а сыновья ханские, остановившись в Евфимиеве монастыре, сняли с великого князя крест-тельник и отослали в Москву к матери и жене пленника.