Однако наряду с неприятными вестями явилась и добрая. Ещё будучи в Новгороде, Иоанн узнал, что в Москву, на службу к нему, прибыли двое татарских царевичей — братья великокняжеского союзника, крымского хана Менгли-Гирея — Айдар и Нордоулат. Они-то и привезли важное сообщение: Менгли-Гирей с помощью турок сверг ставленника Большой Орды Зенебека и вернул себе крымский престол. Обрадовавшись, Иоанн прямо из Новгорода послал в Крым гонца с подарками и поздравлениями союзнику. А теперь в Москве его уже ждало ответное послание Менгли-Гирея. Хан был готов возобновить их союз и просил прислать ему тайно грамоту, скреплённую крестным целованием и печатью, с обещанием дружески принять его в Москве в том случае, если он вновь лишится своего трона, если будет изгнан врагами. Просил клятвы, что русский царь будет обращаться с ним как с государем и содействовать возвращению ему царства. Ещё он просил приглядеть за бежавшими в Москву татарскими царевичами — его братьями Айдаром и Нордоулатом, а также и за свергнутым Зенебеком, не отпускать их в Большую Орду к Ахмату, который сможет использовать их в борьбе против него, Менгли-Гирея.

Царевичи действительно ждали великого князя в Москве. Иоанн принял всех их на службу, устроил в честь них знатный пир. А сам начал готовить ответное посольство в Крым. Вскоре с большой свитой и богатыми дарами туда выехал боярин Иван Звенец. Он вёз письмо с предложением возобновить старый союз и дружбу, быть заедино перед всеми врагами. Иоанн сообщил Менгли-Гирею, что принял к себе на службу его братьев и врага Зенебека, обещал приглядеть за ними и лишить возможности вредить ему. Вёз Звенец и тайную грамоту с золотой печатью и крестным целованием, с обещанием в случае беды принять у себя друга и оказывать ему все требуемые почести.

Тем временем мятежные братья прибыли ко Ржеву во владения князя Бориса Васильевича, где его дожидалась жена с детьми. Иоанн послал к ним на переговоры своего старого верного боярина Андрея Михайловича Плещеева. Послал именно его не случайно — тот был свидетелем и участником междоусобной войны, которую вёл с дядей и братьями ещё их отец. Плещеев был среди тех бояр, которые помогли Василию Тёмному вернуть престол, и за то пользовался большим уважением в великокняжеском семействе. Иоанн наказал боярину узнать, чем недовольны братья, чего хотят. Велел передать, что не желает брани с ними, не хочет напрасно лить русскую кровь, когда кругом и так много настоящих врагов, хочет жить с ними в мире и дружбе.

Князья Андрей и Борис приняли старого боярина уважительно, но мириться отказались, в переговоры вступать не пожелали. Плещеев вернулся ни с чем.