Крымское ханство немедленно выдвинуло своего кандидата на казанский престол. Им стал брат Мухаммеда-Эмина по матери Сагиб Гирей. После смерти хана Ибрагима его жена Нур-Салтан вышла замуж за крымского хана Менгли Гирея. С точки зрения тогдашнего феодального права Сагиб Гирей приходился «седьмой водой на киселе» почившему хану и не имел никаких прав на престол.
Василий III, естественно, тоже нашел кандидата на казанский престол — касимовского царевича Шаха-Али.
Шах-Али имел хорошую родословную, его род происходил от хана Тимура Кутлу. Но к сожалению, его потомки постоянно враждовали с казанской династией Улу Мухаммеда, и к Шаху-Али казанская знать заранее была настроена враждебно.
Однако промосковская партия победила в Казани. И 8 марта 1519 года Шах-Али торжественно выезжает из Москвы в Казань. Фактически же Михаил Юрьевич Захарьин везет на ханство 13-летнего мальчишку. Их сопровождает десятитысячная конная рать.
Шах-Али родился в России и с шестилетнего возраста безвыездно жил в Касимове. Русский летописец описывает его так: «Оный Шея ль зело был взору страшного и мерзкого лица и корпуса, имел уши долгие, на плечах висящие, лице женское, толстое и надменное чрево, короткие ноги, ступени долгие, скотское седалище». Летописец с сарказмом заметил: «Такого им, татарам, нарочно избраша царя в поругание и в посмеяние им».
Тем не менее Захарьину удалось усадить Шаха-Али на престол. После этого Михаил Юрьевич отправился в Москву, а в Казани от имени подростка стал править русский посол Федор Андреевич Карпов.
Но вот в марте 1521 года у стен Казани появляется конкурент — крымский царевич Сагиб Гирей с тремя сотнями крымских татар. Явление Сагиба было подобно искре в пороховом погребе. В Казани начался грандиозный погром. Дома и лавки русских и касимовских купцов были разграблены. Было перебито пять тысяч касимовских татар из ханской гвардии и тысяча русских стрельцов. Однако Шаху-Али удалось бежать с тремя сотнями уцелевших в резне касимовских татар. Сагиб Гирей стал казанским ханом.
Немедленно Сагиб Гирей и его родной брат крымский хан Мухаммед Гирей начали подготовку к большому походу на Русь. В этом походе приняло участие почти все мужское население Крыма и причерноморских степей.
Стотысячное войско Мухаммеда Гирея подошло к Оке 28 июля 1521 года. Русские войска попытались помешать переправе татар, но были разбиты. В бою погибли воеводы Иван Шереметев, Владимир Курбский, Яков и Юрий Замятины, а Федор Лопата попал в плен.
С востока на Русь напал Сагиб Гирей с казанским войском. Он разорил Нижний Новгород и Владимир. Войска братьев соединились у Коломны и двинулись на Москву. Василий III срочно уехал по делам в Волоколамск, поручив оборону столицы своему зятю, татарскому царевичу Петру-Худай-Кулу. В Москве началась паника.
29 июля братья подошли к самой Москве и расположились в селе Воробьеве (на Воробьевых горах). Василий III вынужден был подписать унизительный договор, по которому он формально признавал свою зависимость от крымского хана и должен был платить ему дань «по уставу древних времен», то есть так, как платили ханам Сарайским. Только после этого татары покинули пределы Руси.
Чем занимался в это время Михаил Юрьевич Захарьин, мы не знаем. Скорее всего он был в Москве, поскольку в 1520 и 1521 годах участвовал в переговорах с литовскими послами.
За казанские дела Михаил Юрьевич в 1521 году получит чин боярина. Чтобы не допустить очередного набега татар, великий князь Василий III приказал весной 152-2 года разместить большие силы вдоль Оки. Сам великий князь с братом Юрием стал в Коломне. Большой полк был поставлен «под Давичем», передовой — «на устье Осетра», правой руки — под Голутвиным, левой руки — напротив Ростиславля, сторожевой полк — на Кашире. Сторожевым полком на Кашире командовал Михаил Захарьин.
Военные приготовления Василия III испугали крымского хана, и в 1522 году он не рискнул напасть на Русь.
А в следующем 1523 году хан Мухаммед Гирей двинулся на Астрахань. Войско астраханского хана Хуссейна было разбито, а город взят штурмом. Однако астраханские татары позвали на помощь ногайцев, внезапно напали на крымцев и убили Мухаммеда Гирея. Затем астраханско-ногайское войско вторглось в Крым и опустошило его.
Василий III воспользовался ситуацией и весной 1524 года отправил к Казани большую рать под началом князя Ивана Бельского. В этом походе Михаил Захарьин командовал всей осадной артиллерией.
Сагиб Гирей испугался русских войск и бежал в Константинополь, оставив в Казани тринадцатилетнего племянника Сафа Гирея. Так по крайней мере утверждает русская летопись. На самом деле он уехал в Константинополь, чтобы получить престол в Бахчисарае, освободившийся со смертью брата.
Русская рать осадила Казань, но взять ее не смогла. Мало того, осаждающие оказались в довольно сложном положении — возникли перебои в доставке продовольствия, вокруг сновали конные отряды татар и черкес. Русские были вынуждены заключить довольно выгодный для татар мир, признав Сафа Гирея казанским ханом.