Установление сюзеренитета Ивана III над Казанью заметно повысило его престиж на Востоке. В августе 1490 года мурзы Ногайской орды направили в Москву посольство, предлагая Ивану III союз против «сыновей Ахмата» — то есть против Золотой Орды. Предложение было принято. Более того, Иван позволил своему вассалу, казанскому хану Мухаммеду-Эмину, жениться на дочери ногайского мурзы и отдать в жены другому ногайскому мурзе свою дочь. Поощряя дружественные отношения между ногайцами и Казанью, Иван III, по-видимому, надеялся не только укрепить свое положение по отношению к Золотой Орде, но и открыть новый путь на Ближний Восток через бассейн Яика. Судя по всему, именно этим путем посол Хуссейн-Мирзы, правителя Герата, прибыл 28 сентября 1490 года в Москву.
В 1492 году Москву посетило грузинское (кахетинское) посольство. Как уже отмечалось, по всей видимости, это была не первая грузинская миссия к Ивану III. И это посольство, и предыдущее, должно быть, имели цель поиска защиты православных от натиска мусульман.
Через Крым Иван III старался наладить дружественные отношения с мамлюкским султаном Египта. В 1491 году хан Менгли-Гирей написал Ивану III, что использовал его, Ивана, подношения в качестве подарков оттоманскому султану Баязиду и теперь не имеет ничего подходящего, чтобы послать султану Египта. Он требовал, чтобы Иван III выслал ему соболей и моржовые клыки для отправки в Египет. Судя по всему, Иван III послал Менгли-Гирею то, о чем он просил. В 1493 году в Палестину и Египет отправился русский посол Михаил Мунехин. Главное его поручение, по всей вероятности, заключалось в том, чтобы доставить новые подарки султану Египта, на этот раз без посредничества Менгли-Гирея. После этой поездки Мунехина стали называть Мизиур-Мунехин (от арабского названия Египта — Мизр).
Хотя отношения между Иваном III и Менгли-Гиреем оставались дружественными, среди московских купцов, которые имели дела в Крыму, росло недовольство высокими пошлинами, установленными турками, а также разными притеснениями со стороны турецких чиновников. До появления в Крыму турок русские купцы платили крымскому хану таможенную пошлину (тамгу) в объеме 7 процентов от стоимости товара и специальный налог — 16 денег с человека — мурзе Ширину (Ширины являлись самым могущественным родом среди крымской аристократии). Если русским нужно было отправиться из Каффы морем, они платили тамгу в 5 процентов от стоимости товара, что освобождало их от всех других сборов по возвращении обратно. Но теперь турки увеличили размеры таможенных пошлин и установили новую тамгу в Очакове, которую русским приходилось платить, даже если они там не останавливались. Более того, купцы жаловались, что турки заставляли их работать на строительстве укреплений, например в Азове. Если русский купец заболевал во время пребывания в турецком городе, немедленно опечатывались товары всех членов купеческой общины. После выздоровления купца общине возвращалась только половина товара. Если же купец умирал, весь товар конфисковывали.
Дело дошло до того, что Иван III в 1492 году вообще запретил русским купцам торговать в Крыму. Тогда же через Менг-ли-Гирея он направил письмо султану Баязиду, спрашивая, известно ли тому об обидах, наносимых подданным Ивана III, и предложил прислать турецкого посла в Москву для обсуждения этого вопроса. Не известно, получил ли Иван III ответ от султана, но три года спустя Баязид решил реорганизовать турецкую администрацию в Крыму и отправил одного из своих сыновей, молодого шах-задеха Мехмеда (буквально — «сына верховного правителя»), в Каффу в качестве наместника. К Мехмеду был назначен советник. Менгли-Гирей сообщил Ивану Ill, что Мехмед уполномочен рассмотреть жалобы русских купцов. Вскоре (зимой 1495–1496) Мехмед отправил к Ивану III посла, но того арестовали в Киеве по приказу великого князя Литовского Александра и не позволили проследовать в Москву. Воспользовавшись началом переговоров, которые так и не состоялись, Иван III отправил своего посла Михаила Плещеева в Каффу, чтобы поблагодарить Мехмеда, а затем в Константинополь для переговоров с самим Баязидом.
Плещеев имел от Ивана III строгие инструкции не раскрывать турецким пашам цели своей миссии до встречи с султаном, а также не преклонять перед султаном коленей. Отказ Плещеева подчиниться требованиям турецкого протокола привел пашей в бешенство. На счастье Плещеева, Баязид отличался мягким характером и согласился принять его (в мае 1497 года). В своем ответе Ивану III Баязид сказал, что некоторые жалобы русских купцов лживы, но он тем не менее приказал своему сыну Мехмеду принять строгие меры, чтобы предотвратить притеснения русских купцов и обеспечить справедливое к ним отношение.
В 1499 году Иван III отправил в Константинополь еще одного посла, Александра Голохвастова. Он должен был выразить благодарность Баязиду за его готовность облегчить условия торговли, а также предложить направить в Москву турецкого посла непосредственно от Баязида, а не от Мехмеда Каффского. Баязид хорошо принял Голохвастова, однако в ответе Ивану III, хотя и выказал дружеское расположение, ничего не сказал об отправке посла в Москву. Дальнейшие контакты между Москвой и Константинополем в правление Ивана III осуществлялись через Каффу.
Еще раз возвращаясь к казанским делам, заметим, что власти Москвы над этим ханством бросил вызов тюменский хан Мамук, который заключил соглашение с несколькими ногайскими мурзами и при их поддержке осенью 1495 года напал на Казань. Мамук, несомненно, имел также тайный сговор с некоторыми казанскими мурзами — противниками Мухаммеда-Эмина, но, когда он сам попытался захватить в Казани власть, большинство казанских мурз поднялись против него и отправили гонцов к Ивану III с просьбой посадить на казанский трон нового хана, младшего брата Мухаммеда-Эмина — Абд-ал-Лятифа. Иван III согласился, и в апреле 1496 года московские официальные лица препроводили Абд-ал-Лятифа в Казань и возвели его на престол. Мухаммеду-Эмину Иван III пожаловал в «кормление» три русских города, включая Каширу и Серпухов. Через восемь лет Иван III призвал Абд-ал-Лятифа обратно в Москву, а Мухаммеда-Эмина снова посадил в Казани.