В 1436 году хан Мухаммед лишился престола, будучи низложен претендентами на ханскую власть. Татарские источники, которыми пользовался Ланглее, описывают события, сопровождавшие низложение Улу Мухаммеда, следующим образом. По вступлении на престол Улу Мухаммед приказал отыскать убежище смертельно раненного знаменитого князя Идиге (Едигея), главного приверженца династии Тимура Кутлу, и прикончить его. Сыновья Идиге, бежавшие вместе с племянником Тимура Кутлу Гыяс-эдди-ном в Россию, вернулись с 3-тысячным войском и напали на Улу Мухаммеда. Потерпев поражение, Улу Мухаммед удалился в Крым, победитель же Гыяс-эддин занял Сарай и вступил на ханский престол, но процарствовал недолго и год спустя (в 1437 г.) умер. В ханы был возведен внук Тимура Кутлу, юноша Кичи Мухаммед. «Вслед за этим произошло столкновение между счастливым Кючук Мухаммедом и Улу Мухаммедом… Первый сделал нападение Улу Мухаммед, удалившийся после поражения его Гыяс-эдди-ном в Крым… После нескольких сражений противники заключили договор, по которому все приволжские земли стали принадлежать Кючук Мухаммеду, а Крым достался Улу Мухаммеду. Затем Улу Мухаммед повздорил с эмиром Хайдэром, который пошел тогда к Сейид-Ахмет хану, потомку Тохтамыша, с предложением своих услуг для отнятия трона у обидевшего его Улу Мухаммеда. Они с войском пошли в Крым, а Улу Мухаммед, не надеясь устоять против них, убежал в Казань»[5]. Таким образом, мы видим, что после низложения с престолов ханов Сарайских Улу Мухаммед в течение короткого времени был ханом в Крыму, откуда также был изгнан. Но в Казань он попал из Крыма не сразу. С 3-тысячным войском покинув Крымское ханство, Улу Мухаммед направился в пределы России. Надеясь на гостеприимство великого князя Василия, который получил московский престол из его рук, хан Мухаммед занял город Белев, находившийся на юго-западной окраине Московского государства, близ русско-крымской границы, и решил здесь обосноваться. Но московское правительство, может быть желая показать свою преданность царствовавшему в то время сарайскому хану, противнику Улу Мухаммеда, не оказало поддержки последнему и потребовало удаления его из пределов России. Против Улу Мухаммеда был послан отряд русского войска. 5 декабря 1437 года под Белевом произошла битва — «и множество бысть вой русских, а татар велми мало; и под город приидоша русстии полцы, и выехша татарове и почяша их сечи, а иные побегоша, и убиши Руси много велми… побиша рать русскую, тогда убиша бояр и князей множество, князь великий отъиде в мале дружине»[6].
Имея опыт отторжения от Сарайского ханства независимого Крымского государства, самостоятельность которого была обусловлена договором с Кичи Мухаммедом, и не желая больше оставаться в негостеприимных пределах России в качестве эмигранта, Улу Мухаммед решил отторгнуть от Сарайского ханства другую часть его владений и обосноваться там в качестве независимого государя. С этой целью он составил план восстановления самостоятельного мусульманского государства в Среднем Поволжье, каким было Болгарское царство. Покинув Белев, Улу Мухаммед выступил в Мордовскую землю и, проследовав мимо русской границы, достиг пределов Болгарии. После разгрома 1361 года и недавнего нападения русских под предводительством князя Федора Пестрого (1432), столица края город Булгар лежала в развалинах, и население, отхлынувшее на север за Каму — в более безопасные и глухие места, — стало сосредотачиваться вокруг нового центра — Казани. Поэтому хан Мухаммед избрал столицею своего государства не Булгар, а Казань, и новое ханство получило название Казанского ханства.
Ко времени занятия Улу Мухаммедом Казань была уже крупным городом и унаследовала от Булгара его торговое и политическое значение. При хане Джеляль-уддине в Казани был один из сарайских царевичей — Талыч, который в 1411 году, в согласии с политическими взглядами Джеляль-уддина, оказал поддержку нижегородскому князю Даниилу Борисовичу против Москвы и совершил нападение на Владимир. Русские летописи намекают на то, что Улу Мухаммед взял Казань силою и овладел городом лишь после убийства правившего там местного князя, которого Воскресенская летопись называет «Либеем», то есть князем Али, а Никоновская летопись — князем «Азыем», то есть Газы. Как указал профессор Вельяминов-Зернов, имя Газы является прозвищем («воитель») и впоследствии входило в состав титула ханов Казанских, так что имена князей Али и Газы могли относиться не к двум разным, а к одному и тому же лицу[7]. Он же сделал попытку отождествить Казанского князя Али с князем Галимом, имя которого встречается в одной татарской рукописи в качестве основателя Казани и сына последнего болгарского хана Абдуллаха, погибшего при взятии Булгара Булат-Тимуром. Эту догадку вряд ли можно считать справедливою, так как от разорения Булгара в 1361 году до занятия Казани Улу Мухаммедом прошло около 80 лет, и вряд ли князь Али-Галим мог править в течение столь долгого времени; кроме того, летописи называют его «вотчичем», то есть наследственным князем Казанским, между тем как отец Галима хан Абдуллах был не князем Казанским, а ханом Болгарским.