В Думе прямо объявили о необходимости заключить перемирие с королем, чтоб иметь возможность поуправиться с Казанью и Крымом. Одним из первых распоряжений правительства по смерти Василия было отправление сына боярского Челищева в Крым с известием о восшествии на престол Иоанна. Челищев должен был бить челом Саип-Гирею, чтоб пожаловал нового великого князя, учинил его себе впрок братом и другом, как великий князь Василий был с Менгли-Гиреем; посол должен был также сказать хану: «Если дашь шертную грамоту, то большой посол, князь Стригин-Оболенский, уже ждет в Путивле с большими поминками и немедленно пойдет к тебе». Но, суля неопределенно большие поминки за шертную грамоту, Челищев по-прежнему не должен был ничего давать в пошлину, не должен был давать клятвы, что великий князь будет присылать хану поминки уроком.
В генваре отправлен был Челищев в Крым, а в мае татары уже разоряли русские места по реке Проне, но были прогнаны. Скоро, однако, в самом Крыму встала усобица между ханом Саип-Гиреем и старшим по нем из Гиреев-Исламом; Орда разделилась между соперниками, и это разделение было очень полезно для Москвы, ибо хотя оба хана следовали прежним разбойничьим привычкам и ни от одного из них нельзя было надеяться прочного союза, однако силы разбойников были разделены. Ислам дал обещание королю стоять с ним заодно на всех неприятелей, следовательно, и на московского великого князя и в то же время прислал в Москву с предложением союза; но разумеется, главная цель посылки была требование казны: «Которую казну ты к Саип-Гирею послал, ту казну пришли мне: меня царем учинил турский султан, так ему надобно послать много поминков». В Москве действительно сочли за лучшее послать казну к Исламу, потому что нерасположение Саипа было слишком явно: он пограбил Челищева и всех его людей. Князь Стригин-Оболенский получил вследствие этого приказ ехать из Путивля в Крым к Исламу с большими поминками; очень вероятно, что Оболенский не хотел ехать в Крым, зная, что обыкновенно терпели там московские послы, и он искал всякого рода отговорок, но та, которую он нашел, очень любопытна для нас; он писал великому князю: «Ислам отправил к тебе послом Темеша; по этого Темеша в Крыму не знают и имени ему не ведают; в том бог волен да ты, государь: опалу на меня положить или казнить меня велишь, а мне против этого Исламова посла, Темеша, нельзя идти». Великий князь положил на Оболенского опалу и вместо его велел идти в Крым князю Мезецкому. Начались пересылки с обычным характером: московское правительство требовало от Ислама шертной грамоты, деятельного союза против Литвы; Ислам требовал денег, жаловался, что великий князь не исполнил отцовского завещания, по которому будто бы Василий в знак дружбы отказал ему, Исламу, половину казны своей. В августе 1535 года, когда полки московские шли на защиту Северской стороны от литовцев, крымцы напали на берега Оки, были отражены, но отвлекли московские силы от Северской стороны и облегчили королевскому войску взятие Гомеля и Стародуба. Исламовых послов задержали за это в Москве, но хан отговорился, что воевал московские области не он, а Саип, и послов выпустили. С московскими людьми в Крыму поступали по-прежнему; посол Наумов писал к великому князю: «Приехали к Исламу твои козаки, и вот князья и уланы начали с них платье снимать, просят соболей; я послал сказать об этом Исламу, а князья и уланы пришли на Ислама с бранью: ты у нас отнимаешь, не велишь великому князю нам поминков присылать; а Ислам говорил: какое наше братство! Нарочно великий князь не шлет к нам поминков, не хотя со мною в дружбе и в братстве быть; а князьям сказал: делайте, как вам любо! И они все хотят козаков твоих продать». В Москве, наоборот, старались избегать всякого повода к жалобе со стороны хана: так, когда в Новгороде Северском крымского посла в ссоре покололи рогатиною, то виновники были отосланы головою в Крым к хану. Крымского посла при представлении два раза дарили платьем, сам великий князь подавал ему и товарищам его мед, но требовалось, чтоб посол против государева жалованья на колени становился и колпак снимал.