Kompletigu la sekvan frazon: En 1355, sekvante la otoman
Post la konkero de Gallipoli en la antaŭa jaro, Paul komencis intertraktadojn kun la bizanca imperiestro, John V Palaiologos, por pli proksimiĝo inter Bizanco kaj la Romkatolika Eklezio, kontraŭ okcidenta armea helpo. Paul certigis konsiderindajn koncedojn de la malmola imperiestro, inkluzive de la aktiva antaŭenigo de la latina eklezio kaj eĉ la latina lingvo, la sendado de lia filo Manuel kiel ostaĝo al la papa kortego, kaj la establado de permanenta papa delegacio en Konstantinopolo. Dum sia restado en Konstantinopolo, Paŭlo ankaŭ partoprenis en teologia disputo inter Gregorio Palamas kaj Nikephoros Gregoras. Frue en 1356, Paul, akompanita de la bizanca ambasadoro, la "megas hetaireiarches" Nicholas Sideros, velis al la papa kortego en Avignon, kie ili alvenis frue en junio. Papo Inocenco la 6-a respondis al la ofertoj de la imperiestro per ĝeneralaj vortoj, kaj evitis sin devigi al la sendado de armea helpo, sed sendis Peter Thomas kaj William Conti kiel papajn senditojn al Konstantinopolo. La malsamaj prioritatoj kaj konceptoj de la bizancanoj kaj la latinaj kontribuis al la elĉerpiĝo kaj fina fiasko de la intertraktadoj: letero de Johano la 5-a en 1357 restis sen respondo de Inocento la 6-a ĝis lia morto en 1362.