В церковном отношении ближайшие императоры после Юстиниана держались православия, и временами монофизиты, как то было, например, при Юстине II, подвергались суровым преследованиям. Имеют довольно важное значение отношения Византии во время Маврикия и Фоки к римской церкви. Последняя, в лице папы Григория Великого, высказалась против присвоения константинопольским епископом титула вселенского. В письме к императору Маврикию папа Григорий обвиняет тогдашнего патриарха Иоанна Постника в чрезмерной гордости. "Я должен, - писал папа, - при этом воскликнуть и произнести „о, времена! о, нравы!" (о, tempora, о, mores). В такое время, когда вся Европа подпала под власть варваров, когда города разрушены, крепости срыты, провинции опустошены; когда поля остаются без рук, идолопочитатели свирепствуют и господствуют на погибель верующим, - и в такое-то время священнослужители домогаются тщеславных титулов и гордятся тем, что носят новые, безбожные наименования, вместо того чтобы повергаться в прах, обливаясь слезами. Разве я защищаю, благочестивейший государь, свое собственное дело? Неужели я хочу, говоря так, отомстить личную свою обиду? Нет, я говорю в защиту дела Всемогущего Бога и дела вселенской церкви... Кто оскорбляет святую вселенскую церковь, в чьем сердце бушует гордость, кто хочет пользоваться особенными титулами и, наконец, хочет этим титулом поставить себя выше прерогативы вашей власти - того нужно наказать".
В этом споре папа не добился желаемой уступки и в течение некоторого времени даже не посылал в Константинополь своего представителя. Когда в 602 году там вспыхнула революция против Маврикия в пользу Фоки, который, после безжалостного и зверского умерщвления императора и его семьи, был провозглашен государем, папа Григорий обратился к нему с письмом, тон и содержание которого так мало подходили к этому бессмысленному тирану на византийском престоле. Григорий писал: "Слава в вышних Богу... Да веселятся небеса и да торжествует земля (Пс. 95, II). Весь народ, доселе сильно удрученный, да возрадуется о ваших благорасположенных деяниях!.. Пусть каждый наслаждается свободой под ярмом благочестивой империи. Ибо в том и состоит различие между властителями других народов и императорами, что первые господствуют над рабами, императоры же римского государства повелевают свободными!" По-видимому, на Фоку подобное отношение папы произвело впечатление, так как второй преемник Григория на папском престоле добился того, что Фока запретил константинопольскому патриарху именоваться вселенским и объявил, по словам источника, чтобы "апостольский престол блаженного апостола Петра был главой всех церквей"
Таким образом, в то время как Фока во всех своих внешних и внутренних предприятиях терпел неудачи и вызывал негодование и раздражение своих подданных, отношения его к Риму, основанные на уступках императора папе, были в течение всего царствования дружественными и мирными. В память таких добрых отношений между Римом и Византией на римском Форуме была воздвигнута равеннским экзархом поныне существующая колонна с хвалебной надписью в честь Фоки.