Rampungake ukara ing ngisor iki: Ing 1355, sawise Ottoman
penaklukan Gallipoli ing taun sadurunge, Paul mlebu negosiasi karo kaisar Byzantine, John V Palaiologos, kanggo rapprochement antarane Byzantium lan Gréja Katulik, ing ijol-ijolan kanggo bantuan militer Kulon. Paulus ngamanake konsesi sing cukup saka kaisar sing ditekan, kalebu promosi aktif Gréja Latin lan uga basa Latin, ngirim putrane Manuel minangka sandera menyang pengadilan paus, lan panyiapan legasi paus permanen ing Konstantinopel. Sajrone nginep ing Konstantinopel, Paulus uga melu ing debat teologis antarane Gregory Palamas lan Nikephoros Gregoras. Ing wiwitan taun 1356, Paulus, diiringi duta besar Bizantium, "megas hetaireiarches" Nicholas Sideros, berlayar menyang pengadilan paus ing Avignon, ing ngendi dheweke tekan awal wulan Juni. Paus Innosensius VI mangsuli tawaran kaisar kanthi umum, lan ora nate ngetrapake awake dhewe kanggo ngirim bantuan militer, nanging ngirim Peter Thomas lan William Conti minangka utusan paus menyang Konstantinopel. Prioritas lan konsepsi Bizantium lan Latin sing beda-beda nyumbang kanggo negosiasi sing gagal lan pungkasane gagal: surat 1357 dening John V tetep ora dijawab dening Innocent VI nganti seda ing taun 1362.