Посольство Митяя выехало в Константинополь тотчас после бегства Дионисия. Не желая попасть в руки Мамая, Дионисий избрал окружной путь и потому потерял много времени. Митяй и его свита двинулись кратчайшим путем через Рязань в Орду. Во время следования через степи русское посольство было захвачено татарами и доставлено в ханскую ставку: «И проходящим им Орду, и ту ят (взят. — Р.С.) бысть Митяй Мамаем». Однако Митяй обладал навыками политика, и ему удалось убедить татар, что русская церковь будет следовать курсу митрополита Алексея и позаботится о мире с Ордой. Заверения Митяя не были хитрой уловкой. Начав войну с Литвой, Москва нуждалась в мире на татарской границе. Боярин Кочевин, надо полагать, получил от князя Дмитрия полномочия на мирные переговоры. Соглашение, достигнутое послами при переговорах с ханскими сановниками, было скреплено выдачей ярлыка. По приказу Мамая («Мамаевою дядиною мыслию») хан Тюлякбек выдал ярлык «митрополиту Михаилу», подтвердивший привилегии, полученные митрополитом Алексеем от хана Бердибека. Ярлык освобождал русское духовенство, его дворы и владения от даней, поборов и повинностей в пользу Орды.
Проведя немного времени в ханской ставке, русское посольство было отпущено Мамаем и достигло «моря Кафиньского», иначе говоря, вышло на побережье Черного моря в районе Кафы. Наняв корабль, послы благополучно переплыли «пучину морскую» и добрались до Константинополя. С корабля можно было видеть город. В это самое время Митяй «разболеся в корабли и умре на море». Русский летописец объяснял кончину Митяя вмешательством бога, не желавшего допустить несправедливость, ибо «все же епископи, и презвитери, и священицы того просиша и бога о том молиша, дабы не попустил Митяю в митрополитех быти». Поздний редактор XVI века полагал, что Митяя извели его недруги из посольской свиты, то ли задушившие его, то ли «морьскою водою умориша его».
Смерть Митяя вызвала растерянность послов. Никто не знал, что предпринять. Некоторое время их корабль оставался на виду у города, «не поступая с места ни тамо, ни семо, а инии мнози корабли плаваху мимо его, минующе семо и овамо». Вскоре же послы узнали, что патриарх Макарий, благословивший Митяя на митрополию, низложен и заключен в тюрьму, а его покровитель император Андроник изгнан из Константинополя и бежал под защиту генуэзского флота в Галат. Тогда там же высадились и русские послы. Они привезли мертвого Митяя «в Галату, и ту погребен быть». Не исполнив воли монарха, послы боялись вернуться в Москву. Боярин Кочевин знал о непримиримой вражде князя Дмитрия с проклявшим его Киприаном. Неудача посольства означала бы торжество последнего. Покончить с притязаниями болгарина можно было только одним способом — поставив законного митрополита Киевского и всея Руси из числа преданных князю Дмитрию лиц. Церковь оставалась без пастыря более года, и посольство решило не возвращаться в Москву без митрополита. Но вопрос о том, кому принять сан, вызвал яростные споры.
Светские власти не включили в посольство ни одного лица, который был бы саном выше Митяя. По этой причине в Византию прибыли сразу три архимандрита и ни одного епископа. Митяй не пользовался авторитетом у сотоварищей. Будучи старше Митяя и имея за плечами многие годы монашеской жизни, архимандриты полагали, что смогут исполнять обязанности митрополита гораздо лучше, чем умерший «новик». Наибольшие права имел столичный архимандрит Иван, «общему житию начальник на Москве». Переяславский и коломенский архимандриты стояли ступенькой ниже на иерархической лестнице духовных чинов. Однако старейшинство в посольстве было предоставлено не духовной, а светской особе. Боярин Юрий Кочевин представлял особу великого князя, а потому ему принадлежало решающее слово. Между послами возникли «распри и разгласив: одни хотеша Ивана в митрополиты, а друзии Пимена; и, много думавше промежи собою, и яшася бояре за Пимена, а Ивана оставиша поругана и отъринуша и».
Самым подходящим кандидатом в митрополиты был архимандрит Иван. В Москве его поддержали бы Сергий и епископы. Но в Константинополе верх взяли бояре — сторонники Пимена. Среди митрополичьих бояр старшим был Федор Шолохов. Сохранился родословец Шолоховых-Чертовых, в котором записано, что родоначальник Шолоховых Алексей, введенный дьяк Василия II, был якобы за измену приговорен к смерти, но прощен и передан с вотчиной в службу митрополиту Ионе, просившему о его помиловании. По-видимому, родословец отразил в себе семейные предания, не отличавшиеся точностью. Митрополит Иона возглавлял церковь не при Василии II, а при его сыне Иване III, в конце XV века. Федор же Шолохов был принят на службу в митрополичий дом Митяем — любимцем княза Дмитрия. Вместе с ним митрополичьими боярами числились братья Коробьины, Н. Бармин, С. Кловыня. Однако решающий голос принадлежал не им, а великокняжескому боярину Юрию Кочевину.
Потерпев поражение, Иван Петровский пригрозил, что донесет на согрешивших против истины послов то ли патриарху, то ли московским властям. «Аз, — сказал он, — не обинуяся, възглаголю на вы, единаче есте не истиньствуете ходяще!» Тогда Кочевин по совету архимандрита Пимена выбрал удобный момент и, «пришедше, возложиша руце на Ивана и яша его, и посадиша его в железа», чтобы не мог бежать с корабля.
Князь Дмитрий снабдил своего любимца чистой «хартьей», запечатанной великокняжеской печатью. Найдя в казне Митяя эту грамоту, Пимен и его советники написали подложную. Из нее следовало, что московский князь прислал в Константинополь на поставление не Митяя, а Пимена, «того бо единого избрах на Руси и паче того иного не обретох».
Однако обмануть Синод с помощью подложной грамоты послам было довольно трудно. Во-первых, патриаршая канцелярия располагала точными данными о том, что на митрополию в Москве назначен Михаил, а не Пимен. Во-вторых похороны Митяя в Галате не могли остаться тайной для Константинополя. В-третьих, в приемной у патриарха послы столкнулись лицом к лицу с прибывшим из Киева Киприаном, доказывавшим свое исключительное право на митрополичий стол.
Преодолеть все преграды послам помогли деньги. Провожая Митяя, великий князь напутствовал его словами: «Аще будет оскудение или какова нужа и надобе заняти или тысящу сребра, или колико, то се вы буди кабала моя и с печатию». Митяй не смог воспользоваться предоставленным ему правом. Но «кабала» пригодилась Пимену. В обычных условиях послы расходовали на подарки и подкуп до тысячи рублей, как это было в 1389 году. Пимен же далеко превысил сумму, определенную князем. По Никоновской летописи, послы заняли по кабалам до 200 тысяч рублей. Но эта цифра лишена достоверности. Автор тверской летописи записал такой слух: «Взято было боле 70 и 6 долгу». Что означали эти цифры? Сотни или тысячи рублей? Скорее всего, ни то, ни другое. Посол Кочевин и Пимен заняли «у фряз и у бесермен» деньги, обращавшиеся в Византии, и обозначенные в кабале цифры соответствовали византийским или итальянским счетным единицам, непонятным для русского книжника. Ростовщики ссужали русским деньги под большие проценты, и московская казна не могла оплатить непомерный долг в течение многих лет. Когда Пимен вновь отправился в Византию в 1389 году, кредиторы-генуэзцы захватили его и держали в узах, пока он не заплатил им «довольну мзду».
8 июне 1380 года Синод избрал на патриарший стол Нила. Новый патриарх должен был выслушать и Киприана, и русских послов. Киприан просил, чтобы в соответствии с постановлением Синода 1375 года ему предоставили власть над Великой Русью. Русские послы добивались, чтобы Киприан был лишен литовской митрополии. Нил обещал провести тщательное расследование, но при этом дал понять Киприану, что тот может лишиться всего. Трезво оценив ситуацию, Киприан несколько дней спустя явился в Синод и заявил, что отказывается от суда и «готов довольствоваться только частию (митрополии. — Р.С.), в которую поставки, а от прочего уже отказался». Видя, что чиновники Синода подкуплены, Киприан вскоре тайно убежал, ни с кем не простившись.