Еще в 1586 году приезжал в Москву за милостынею Антиохийский Патриарх Иоаким, коему Царь изъявил желание учредить Патриархию в России: Иоаким дал слово предложить о том Собору Греческой Церкви и предложил с усердием, славя чистоту нашей Веры. В Июле 1588 года, к великому удовольствию Феодора, явился в Москве и Патриарх Константинопольский, Иеремия. Вся столица была в движении, когда сей главный Святитель Христианский (ибо престол Византийского Архиерейства уже давно считался первым), старец знаменитый несчастием и добродетелию, с любопытством взирая на ее многолюдство и красоту церквей, благословляя народ и душевно умиляясь его радостным приветствием, ехал на осляти к Царю по стогнам Московским; за ним ехали на конях Митрополит Монемвасийский (или Мальвазийский) Иерофей и Архиепископ Элассонский Арсений. Когда они вошли в златую палату, Феодор встал, чтобы встретить Иеремию в нескольких шагах от трона; посадил близ себя; с любовию принял дары его: икону с памятниками Страстей Господних, с каплями Христовой крови, с мощами Св. Царя Константина — и велел Борису Годунову беседовать с ним наедине. Патриарха отвели в другую комнату, где он рассказал Борису свою историю. Лет десять управляв Церковию, Иеремия, обнесенный каким-то злым Греком, был сослан в Родос, и Султан, вопреки торжественному обету Магомета II не мешаться в дела Христианской духовной власти, беззаконно дал Патриаршество Феолипту. Чрез пять лет возвратили изгнаннику сан Иерарха; но в древнем храме Византийских Первосвятителей уже славили Аллу и Магомета: сия церковь сделалась мечетию. «Обливаясь слезами, — говорил Иеремия, — я вымолил у жестокого Амурата дозволение ехать в земли Христианские для собрания милостыни, чтобы посвятить новый храм истинному Богу в древней столице Православия: где же, кроме России, мог я найти усердие, жалость и щедрость?» Далее, беседуя с Годуновым, он похвалил мысль Феодорову иметь Патриарха Российского; а лукавый Годунов предложил сие достоинство самому Иеремии, с условием жить в Владимире. Иеремия соглашался, но хотел жить там, где Царь, то есть в Москве: чего не хотел Годунов, доказывая, что несправедливо удалить Иова, мужа святого, от Московского храма Богоматери; что Иеремия. не зная ни языка, ни обычаев России, не может быть в духовных делах наставником Венценосца без толмача, коему непристойно читать во глубине души Государевой. «Да исполнится же воля Царская! — ответствовал Патриарх, — уполномоченный нашею Церковию, благословлю и поставлю, кого изберет Феодор, вдохновенный Богом». В выборе не было сомнения; но для обряда Святители Российские назначали трех кандидатов: Митрополита Иова, Архиепископа Новагородского Александра, Варлаама Ростовского, и поднесли доклад Царю, который избрал Иова. 23 Генваря (1589), после Вечерни, сей наименованный Первосвятитель, в епитрахили, в омофоре и в ризе, пел молебен в храме Успения, со всеми Епископами, в присутствии Царя и бесчисленного множества людей; вышел из алтаря и стал на амвоне, держа в руке свечу, а в другой письмо благодарственное к Государю и к Духовенству. Тут один из знатных сановников приближился к нему, держа в руке также пылающую свечу, и сказал громко: «Православный Царь, Вселенский Патриарх и Собор освященный возвышают тебя на престол Владимирский, Московский и всея России». Иов ответствовал: «Я раб грешный; но если Самодержец, Вселенский Господин Иеремия и Собор удостаивают меня столь великого сана, то приемлю его с благодарением»; смиренно преклонил главу, обратился к Духовенству, к народу, и с умилением произнес обет ревностно блюсти вверенное ему от Бога стадо. Сим исполнился устав избрания , торжественное же посвящение совершилось 26 Генваря, на Литургии, как обыкновенно ставили Митрополитов и Епископов, без всяких новых обрядов. Среди Великой , или Соборной, церкви, на помосте, был изображен мелом орел двоеглавый и сделан феатрон о двенадцати степенях и двенадцати огненниках : там старейший Пастырь Восточного Православия, благословив Иова как сопрестольника великих отцов Христианства и возложив на него дрожащую руку, молился, да будет сей Архиерей Иисусов неугасаемым светильником Веры.
Имея на главе митру с крестом и с короною, новопоставленный Московский Патриарх священнодействовал вместе с Византийским; и когда, отпев Литургию, разоблачился, Государь собственною рукою возложил на него драгоценный крест с животворящим древом, бархатную зеленую мантию с источниками, или полосами, низанными жемчугом, и белый клобук с знамением креста; подал ему жезл Св. Петра Митрополита и в приветственной речи велел именоваться главою Епископов, отцем отцев, Патриархом всех земель Северных, по милости Божией и воле Царской. Иов благословил Феодора и народ; а лики многолетствовали Царю и двум Первосвятителям, Византийскому и Московскому, которые сидели с ним рядом на стульях. Вышед из церкви, Иов, провождаемый двумя Епископами, Боярами, многими чиновниками, ездил на осляти вокруг стен Кремлевских, кропя их Святою водою, осеняя крестом, читая молитвы о целости града, и вместе с Иеремиею, со всем Духовенством, Синклитом, обедал у Государя.
Чтобы утвердить достоинство и права Российского священноначалия, написали уставную грамоту, изъясняя в ней, что Ветхий Рим пал от ереси Аполлинариевой , что Новый Рим , Константинополь, обладаем безбожными племенами Агарянскими; что третий Рим есть Москва; что вместо лжепастыря Западной Церкви, омраченной духом суемудрия, первый вселенский Святитель есть Патриарх Константинопольский, второй Александрийский, третий Московский и всея России , четвертый Антиохийский, пятый Иерусалимский; что в России должно молиться о Греческих, а в Греции о нашем, который впредь, до скончания века, будет избираем и посвящаем в Москве независимо от их согласия или одобрения. К наружным отличиям сего Архипастыря нашей церкви прибавили следующие: «Выход его должен быть всегда с лампадою, с пением и звоном; для облачения иметь ему амвон о трех степенях; в будни носить клобук с Серафимами и крестами обнизными, мантии объяринные и всякие иные с полосами; ходить в пути с крестом и жезлом; ездить на шести конях». Тогда же Государь с двумя Патриархами соборно уложил быть в России четырем Митрополитам : Новогородскому, Казанскому, Ростовскому и Крутицкому; шести Архиепископам : Вологодскому, Суздальскому, Нижегородскому, Смоленскому, Рязанскому, Тверскому — и осьми Епископам : Псковскому, Ржевскому, Устюжскому, Белозерскому, Коломенскому, Северскому, Дмитровскому.
Участвуя более именем, нежели делом, в сих церковных распоряжениях, Иеремия, Митрополит Монемвасийский и Архиепископ Элассонский ездили между тем в Лавру Сергиеву, где, равно как и в Московских храмах, удивлялись богатству икон, сосудов, риз служебных; в столице обедали у Патриарха Иова, славя мудрость его беседы; славили также высокие достоинства Годунова и редкий ум старца, Андрея Щелкалова; всего же более хвалили щедрость Российскую: ибо их непрестанно дарили, серебряными кубками, ковшами, перлами, шелковыми тканями, соболями, деньгами. Представленные Царице, они восхитились ее святостию, смиренным величием, ангельскою красотою, сладостию речей, равно как и наружным великолепием. На ней была корона с двенадцатью жемчужными зубцами, диадема и на груди златая цепь, украшенная драгоценными каменьями; одежда бархатная, длинная, обсаженная крупным жемчугом, и мантия не менее богатая. Подле Царицы стоял Царь, а с другой стороны Борис Годунов, без шапки, смиренно и благоговейно; далее многие жены знатные, в белой одежде, сложив руки. Ирина с умилением просила Святителей Греческих молить Бога, чтобы он даровал ей сына, наследника Державе — «и все мы, тронутые до глубины сердца (говорит Архиепископ Элассонский в описании своего путешествия в Москву) вместе с нею обливаясь слезами, единогласно воззвали ко Всевышнему, да исполнится чистое, столь усердное моление сей души благочестивой!» — Наконец Государь (в мае 1589) отпустил Иеремию в Константинополь с письмом к Султану, убеждая его не теснить Христиан, и сверх даров послал туда 1000 рублей, или 2000 золотых монет Венгерских, на строение новой Патриаршей церкви, к живейшей признательности всего Греческого Духовенства, которое, Соборною грамотою одобрив учреждение Московской Патриархии, доставило Феодору сию хартию (в Июне 1591) чрез Митрополита терновского, вместе с Мощами Святых и с двумя коронами, для Царя и Царицы.