Ослабление великокняжеской власти проявилось и в неспособности выстроить отношения с Улу-Мухаммедом, который в 1436 г. был смещен с ханского престола Большой Орды, бежал в Крым, а потом вынужден был покинуть и его. Всего с 3000 всадников в конце 1437 г. он попытался утвердиться в городе Белев на Оке. Белев был пограничной территорией под властью ВКЛ, и Улу-Мухаммед предлагал установить дружественные отношения создаваемого им нового княжества с Москвой. Тем не менее против него было двинуто большое московское войско, которое потерпело сокрушительный разгром от многократно уступавшего по численности противника. Улу-Мухаммед не стал дожидаться нового похода московских или литовских войск и ушел на Среднюю Волгу, где основал Казанское ханство (1438). Подорванный военный авторитет Москвы и испорченные личные отношения привели к тому, что новое Казанское ханство сразу повело себя агрессивно по отношению к соседним русским землям. Уже весной 1439 г. казанский хан захватил Нижний Новгород и сжег посады вокруг Московского кремля. В 1444−1445 гг. Улу-Мухаммед предпринял еще один большой рейд на Москву. Возглавивший поход против него Василий II проиграл сражение у Суздаля 7 июля 1445 г. и попал в плен.
После этого соправитель Василия II Дмитрий Шемяка объявил себя единственным великим князем. Он выпускает деньги с амбициозным титулом «осподарь всея Руси» (т. е. уже не довольствуясь собственно Московским великокняжеским титулом) и отправляет к Казанскому хану своего дьяка Федора Дубенского с доносом («со всем лихом») на Василия II. Поняв, что выкупать из плена его никто не собирается, Василий II поклялся Улу-Мухаммеду собрать выкуп самостоятельно, и 1 октября 1445 г. хан его отпустил в Москву в сопровождении эскорта в 500 человек. Так начал реализовываться новый политический сценарий вассальных отношений, хотя трудно определенно сказать, кто же именно играл роль вассала, а кто синьора. С одной стороны, Василий II изгоняет Дмитрия Шемяку из Москвы и начинает княжить с санкции хана Казани (даже не Золотой Орды). С другой стороны, формальная зависимость от Казанского ханства приняла форму вассальных отношений казанцев от Москвы: огромный выкуп за великого князя выплачивали в значительной мере «натурой», передав в «кормление» казанским князьям многие города. А сыну Улу-Мухаммеда Касиму был отдан целый Мещерский край (в 300 км к юго-востоку от Москвы), где он основал Касимовское ханство в вассальной зависимости от ВКМ. Получалось, что Казанский хан использовал свое превосходство, чтобы добиться вассального статуса от Московского князя…
Тем не менее контраст между демонстративными претензиями Дмитрия Шемяки на самодержавие во всех русских землях и формальными уступками Василия II по отношению к Казанскому ханству был разителен. Дмитрий Шемяка начал распространять слухи, что Василий II готовит передачу всех русских земель под власть хана. Ему удалось заручиться поддержкой князей можайского и тверского и некоторых недовольных московских бояр и совершить государственный переворот — новшество в московской политической традиции. В ночь на 13 февраля 1446 г. войска Дмитрия Шемяки без боя заняли Москву, а в ночь на 14 февраля Василий II с семьей был захвачен в Троицком монастыре, ослеплен и сослан в Вологду, причем он присягнул Шемяке как великому князю.