Столпы православной церкви Востока нимало не сочувствовали русским проектам, но не хотели и открыто отклонить их. Торг из-за патриаршего сана мог обернуться для них большими выгодами. В Москве стали ждать, как отреагирует константинопольский патриарх Феолит. Его гонец явился в Москву с грамотой, содержащей обычную просьбу о помощи, но на словах он передал весть, которую в Москве давно ожидали. Царьградский и антиохийский патриархи, заявил он, послали за другими патриархами, чтобы решить московское дело на соборе.
Византиец не желал вести с Москвой письменные переговоры об учреждении патриаршества, однако дни его правления были сочтены. Турки низложили Феолита и назначили на его место патриарха Иеремию. Новый глава вселенской церкви начал с того, что отправился на Русь.
В Москве ничего не знали о происшедших в Царьграде переменах и на первых порах даже заподозрили Иеремию в самозванстве. Но подозрения скоро рассеялись, и 21 июля патриарх удостоился аудиенции в Кремле. После представления царю Иеремию отвели в особую палату, где он имел беседу с глазу на глаз с правителем Борисом Годуновым и «канцлером» А. Я. Щелкаловым. Беседа выявила крайне неприятные факты. Русские ждали, что патриарх привез с собой постановление Вселенского собора. Оказалось же, что дело не сдвинулось с мертвой точки.
Аудиенция в Кремлевском дворце положила начало трудным переговорам, тянувшимся более полугода. Ход их получил в источниках неодинаковое освещение. Официальный отчет, составленный Посольским приказом, излагал историю переговоров с большими пропусками. Русские церковные писатели не останавливались перед искажениями. Они утверждали, будто Иеремия сразу уведомил царя о состоявшемся решении Вселенского собора учредить на Москве патриаршество. Помощники патриарха Иеремии — митрополит Дорофей и архиепископ Арсений, участвовавшие в переговорах с византийской стороны, изложили свои впечатления в записках. Их суждения расходились в самых существенных пунктах.
Архиепископ Арсений Елассонский описал путешествие в Московию в виде послания, адресованного некоему «другу» на Востоке. Сочинение Арсения прославляло патриарха Иеремию, этого «мудреца» и «нового Иова». Дифирамбы должны были успокоить недовольных членов Вселенского собора, указавших на незаконность действий Иеремии в Москве. Свои впечатления он излагает в стихах, поскольку виденное, заявлял автор, не поддается прозаическому описанию. Нетрудно обнаружить истоки вдохновения грека. Когда патриарх Иеремия получил аудиенцию в Кремле, царь щедро одарил его спутников, за исключением одного Арсения. Такая немилость была вызвана тем, что Арсений уже был однажды в Москве и получил большую сумму на помин души царя Ивана, но распорядился деньгами не так, как следует. Порядочные поминки Арсений мог сотворить лишь в своей епархии, а между тем, покинув Русь, архиепископ остался в неприятельской Литовской земле. Но в ходе переговоров об учреждении патриаршества Арсений оказал московитам столь важные услуги, что отношение к нему полностью переменилось. На прощальной аудиенции в честь Иеремии царь сказал Арсению: «Твердо надейся, что я никогда не оставлю тебя без помощи: многие города с их областями я тебе поручу и ты будешь управлять ими в качестве епископа». Со временем это обещание было исполнено: он стал епископом при Архангельском соборе в Кремле. Арсений помог московитам довести до благополучного конца переговоры с Иеремией в Москве. Затем он выехал в Константинополь, где Иеремии предстояло созвать Вселенский собор и добиться от него санкции на учреждение московского патриаршества. Перо Арсения немало помогло ему в этом деле. В своем стихотворном сочинении он постарался представить поведение патриарха в Москве безупречным.
Другой спутник Иеремии — митрополит Монемвасийский Дорофей — включил сведения о путешествии в Москву в текст составленного им Хронографа. Его краткая и лишенная каких бы то ни было литературных красот заметка представляется более достоверной, нежели стихотворные сочинения Арсения. Подлинной причиной путешествия Иеремии в Москву, сообщил Дорофей, было то, что константинопольское патриаршество из-за долгов оказалось в трудном финансовом положении. Переговоры в Москве по поводу субсидий сразу зашли в тупик, поскольку русские власти предварительно потребовали решить вопрос об учреждении у них патриаршества.
Появление Иеремии в Москве поставило правителя перед выбором. Можно было отпустить патриарха без субсидий и тем самым утратить возможности, связанные с первым посещением Руси главой вселенской церкви. Можно было дать ему богатую милостыню, но это не гарантировало успеха в достижении основной цели. Можно было, наконец, задержать Иеремию и заставить его уступить. В Москве избрали последний путь. На то были особые причины.