Инициатива Порты была встречена в Москве с явным интересом. В условиях нараставшей напряженности в русско-литовских отношениях Ивану III было важно, чтобы "салтан турской" оказался "недругом” великому князю литовскому. Ободренная знаками внимания, Порта вскоре сделала следующий шаг, заявив о готовности обменяться послами. Об этом в марте 1488 г. сообщил крымский хан Менгли-Гирей. В ответ на настойчивые просьбы русских представителей в Крыму дать более подробные сведения о том, "каковы дружбы" ищет султан, хан, со ссылкой на известия, привезенные его гонцом из Стамбула, писал: "…Турецкое слово таково: коли князь велики тебе Мен[гли] Гирею друг да брат, и яз потомуж хочю с ним быти в дружбе и в братстве. А прикажу еще о том к брату своему великому князю своими послами, {135} чтоб к турскому послал и о том зауморщины бы его людем не было…" Направленная султану грамота от 31 августа 1492 г. считается первым письменным документом начинавшихся межгосударственных отношений. Она посвящена в основном вопросам торговли между Московским государством и Османской империей и имеет весьма примечательное начало, где Иван III, отметив, что "меж нас с тобою наши люди не ежживали нашего здоровья видети", добавляет: "только наши гости из наших земель в твои земли ездят, нашим и вашим людям много корысти бывало".
Реакция Порты на послание Ивана III определилась к началу 1494 г., летом того же года султанский ответ был передан через крымского хана в Москву. Суть его Менгли-Гирей изложил так: "Посол мой болшой пойдет и яз тогда ответ пошлю". Одновременно Баязид II назначил в качестве наместника в Кафу одного из своих сыновей — Мехмеда. Посольство в конечном итоге было решено послать от его имени. Однако по указанию великого князя литовского, явно встревоженного перспективой сближения Москвы и Стамбула, киевский наместник не пропустил ни посла, ни сопровождавших его турецких купцов под весьма неуклюжим предлогом: "чтобы они наших земель государственных не пересматривали". Посол шахзаде был вынужден вернуться в Кафу, но о поручениях, данных ему, московское правительство получило довольно полное представление.
Готовность Порты решать столь важные вопросы была должным образом оценена Иваном III, и он решил не медлить с направлением своего посольства. Во главе его был поставлен представитель видного боярского рода стольник Михаил Андреевич Плещеев. Маршрут поездки предполагал посещение по дороге в Стамбул Кафы и встречу с шахзаде Мехмедом. В Стамбуле посол был принят Баязидом, который вручил ему ответные грамоты на имя Ивана III, но своего посла в Москву султан тогда не отправил.