Иоанн немедленно уведомил о сем счастливом происшествии Менгли-Гирея и в особенности Царицу Нурсалтан, умную, честолюбивую, желая, чтобы она, из благодарности за ее сына, им возвеличенного, способствовала твердости союза между Россиею и Крымом. Сия искренняя, взаимная приязнь не изменялась. Великий Князь уведомлял Менгли-Гирея о замыслах Ханов Ординских, о частых их сношениях с Казимиром; и, сведав, что они двинулись к Тавриде, отрядил Козаков с Нордоулатом, бывшим Царем Крымским, на Улусы Золотой Орды; велел и Магмед-Аминю тревожить ее нападениями; советовал также Менгли-Гирею возбудить Ногаев против сыновей Ахматовых. Сообщение между Тавридою и Россиею подвергалось крайним затруднениям, ибо Волжские Татары хватали в степях, кого встречали, на берегах Оскола и Мерли: для того Иоанн предлагал Хану уставить новый путь через Азов с условием, чтобы Турки освобождали Россиян от всякой пошлины. Сия безопасность пути нужна была не только для государственных сношений и купцев, но и для иноземных художников, вызываемых Великим Князем из Италии и ездивших в Москву через Кафу. Кроме обыкновенных гонцов, отправлялись в Тавриду и знаменитые Послы: в 1486 году Семен Борисович, в 1487 Боярин Дмитрий Васильевич Шеин, с ласковыми грамотами и дарами, весьма умеренными; например, в 1486 году Иоанн послал Царю три шубы - рысью, кунью и беличью, - три соболя и корабельник, жене его и брату, Калге Ямгурчею, по корабельнику, а детям по червонцу. За то и сам хотел даров: узнав, что Царица Нурсалтан достала славную Тохтамышеву жемчужину (которую, может быть, сей Хан похитил в Москве при Димитрии Донском), он неотступно требовал ее в письмах и наконец получил от Царицы. - Как истинный друг Мангли-Гирея, Иоанн способствовал его союзу с Королем Венгерским и не дал ему сделать важной политической ошибки. Сей случай достопамятен, показывая ум Великого Князя и простосердечие Хана. Братья Менгли-Гиреевы, Айдар и Нордоулат, добровольно приехав в Россию, уже не имели свободы выехать оттуда. Хан Золотой Орды, Муртоза, желал переманить Нордоулата к себе и (в 1487 году) прислал своего чиновника в Москву с письмами к нему и к Великому Князю, говоря первому: «Брат и друг мой, сердцем праведный, величеством знаменитый, опора Бесерменского Царства! Ты ведаешь, что мы дети единого отца; предки наши, омраченные властолюбием, восстали друг на друга: немало было зла и кровопролития; но раздоры утихли: следы крови омылися млеком, и пламень вражды погас от воды любовной. Брат твой, Менгли-Гирей, снова возбудил междоусобие: за что господь наказал его столь многими бедствиями. Ты, краса отечества, живешь среди неверных: сего мы не можем видеть спокойно и шлем твоему величеству тяжелый поклон с легким даром чрез слугу, Ших-Баглула: открой ему тайные свои мысли. Хочешь ли оставить страну злочестия? Мы пишем о том к Ивану. Где ни будешь, будь здрав и люби наше братство». Письмо к Великому Князю содержало в себе следующее: «Муртозино слово Ивану. Знай, что Царь Нордоулат всегда любил меня: отпусти его, да возведу на Царство, свергнув моего злодея, Менгли-Гирея. Удержи в залог жену и детей Нордоулатовых: когда он сядет на престол, тогда возьмет их у тебя добром и любовию». Великий Князь посмеялся над гордостию Муртозы; задержав его Посла, известил о том Менгли-Гирея и прибавил, что Король Польский тайно зовет к себе другого брата Ханского, Айдара. Но Менгли-Гирей, не весьма прозорливый, скучая множеством забот, сам желал уступить Нордоулату половину трона, чтобы он, вместе с ним Царствуя, своим умом и мужеством облегчил ему тягость власти. «Отправь его ко мне, - писал Менгли-Гирей к Иоанну: - мы забудем прошедшее. Айдара же не боюсь: пусть идет, куда хочет». Великий Князь ответствовал, что не может исполнить требования столь неблагоразумного; что властолюбие не знает ни братства, ни благодарности; что Нордоулат, быв сам Царем в Тавриде, не удовольствуется частию власти, имея дарования и многих единомышленников; что долг приязни есть остерегать приятеля и не соглашаться на то, что ему вредно. Сии представления образумили и, может быть, спасли Менгли-Гирея.
Несчастная судьба Алегама оскорбила Шибанских и Ногайских Владетелей, связанных с ним родством: Царь Ивак, Мурзы Алач, Муса, Ямгурчей и жена его прислали в Москву грамоты, убеждая в них освободить сего пленника. Ивак писал к Великому Князю: «Ты мне брат: я Государь Бесерменский, а ты Христианский. Хочешь ли быть в любви со мною? Отпусти моего брата, Алегама. Какая тебе польза держать его в неволе? вспомни, что ты, заключая с ним договоры, обещал ему доброжелательство и приязнь». Мурзы изъявляли в своих письмах более смирения, говоря, что они шлют Великому Князю тяжелые поклоны с легким даром и ждут от него милости; что отцы их жили всегда в любви с Государями Московскими; что обстоятельства удаляли юрт Иваков от пределов России, но что сей Царь, победив недругов, снова к ней приближился и хочет Иоанновой дружбы. Послы Ногайские желали еще, чтобы купцы их могли свободно приезжать к нам и торговать везде без пошлин. Государь велел объявить им следующий ответ: «Алегама, обманщика и клятвопреступника, мною сверженного, не отпускаю; а другом вашим быть соглашаюсь, если Царь Ивак казнит разбойников, людей Алегамовых, которые у него живут и грабят землю мою и сына моего, Магмет-Аминя; если возвратит все похищенное ими ли не будет впредь терпеть подобных злодейств». В ожидании сего требуемого удовлетворения Иоанн задержал в Москве одного из Послов, отпустил других и велел, чтобы Ногайцы ездили в Россию всегда чрез Казань и Нижний, а не Мордовскою землею, как они приехали. Сии сношения продолжались и в следующие годы, представляя мало достопамятного для Истории. Видим только, что Орда Ногайская, кочуя на берегах Яика и близ Тюменя, имела разных Царей и сильных Мурз, или Князей Владетельных; называясь их другом, Иоанн говорил с ними языком повелителя; дозволил Князю Мусе, внуку Эдигееву и племяннику Темирову, выдать дочь свою за Магмет-Аминя, но не велел последнему выдавать сестры за сына Мурзы Ногайского, Ямгурчея, коего люди, вместе с жителями Астраханскими, грабили наших рыболовов на Волге; несмотря на все убедительные просьбы Ногайских Владетелей, держал Алегама в неволе, ответствуя: «из уважения к вам даю ему всякую льготу»; посылал к ним гонцов и дары, ипрские сукна, кречетов, рыбьи зубы, не забывая и жен их, которые в своих приписках именовались его сестрами, но; строго наблюдая пристойность в Дворских обрядах и различая Послов, Великий Князь изъяснялся с Ногайскими единственно через второстепенных сановников, Казначеев и Дьяков. Главною целию Иоанновой Политики в рассуждении сего кочевого народа было возбуждать его против Ахматовых сыновей и не допускать до впадения в землю Казанскую, где Магмет-Аминь Царствовал как присяжник и данник России: ибо в тогдашних бумагах находим жалобу Магмед-Аминя на чиновника Московского, Федора Киселева, который сверх обыкновенных пошлин взял у жителей Цывильской области несколько кадок меда, лошадей, куниц, бобров, лисьих шкур и проч.