В начале 1198 г. византийский император письменно поздравил нового папу римского с восшествием на папский престол и предложил, чтобы они вместе приняли меры к развитию церкви и империи. Устные сообщения о деталях союза были доверены им своим представителям Иоанну Грегориосу или Георгиосу и Ильдебарду. Иннокентий ответил в августе, побуждая Алексея вернуться в лоно церкви и продемонстрировать свою добрую волю, оказав помощь осажденным государствам крестоносцев, что стало бы поступком, который, по его мнению, богатство, мощь и близость к Святой земле Византии делали весьма подходящим. По заявлению папы, все христиане ужасаются тому, что греки продолжают бессмысленно придерживаться своей ереси и предали Гроб Господень. Дополнительные тайные политические переговоры были доверены легату – поддьякону Альбертину. Отправив одновременно письмо патриарху Константинопольскому, папа изложил теорию о главенстве папской власти над церковью на основании того, что папа римский является наследником апостола Петра, и утверждал, что патриарх должен проявить инициативу в объединении своей паствы с Римом, а также повлиять на императора таким образом, чтобы тот согласился на просьбы папы. И хотя эта теория о верховенстве папской власти отталкивала византийцев, переговоры о создании общего фронта против Гогенштауфена, вероятно, имели успех, так как эта тема больше не возникала в более поздней переписке, нет и дальнейших ссылок на какие-либо тайные обсуждения.
В феврале 1199 г. Алексей III прислал ответ, взяв на себя большие обязательства, чем папа имел право ожидать. Император заявил, что спасение Святой земли должно дождаться избранного Господом часа или, по крайней мере, такого момента, когда уменьшатся вероятные расходы денег и войск, в то время как воссоединение церквей может осуществиться лишь путем воздействия Святого Духа на обе стороны. Но он все же предложил, чтобы Иннокентий созвал церковный собор, на котором будет присутствовать и Православная церковь. Патриарх Иоанн X Каматир написал в это же время папе, что у него есть сомнения относительно главенства Рима; по его мнению, латинская церковь виновата в расколе, так как ввела знаменитый пункт о filioque (который гласит, что Святой Дух исходит от Отца и от Сына) в Никейский Символ веры. 12 ноября 1199 г. папа римский прислал патриарху в ответ многословное подробное исследование божественного установления папской власти апостолом Петром и его последователями; Иннокентий уведомил патриарха о том, что тот должен приехать на собор, приняв главенство Рима как основу для дальнейших переговоров. На следующий день Иннокентий написал Алексею письмо, в котором упрекнул его за нелогичную отсрочку завоевания Иерусалима, так как никто не узнает волю Господню, если не предпримет попытку. Порадовавшись тому, что император одобрил идею созвать церковный собор, папа римский повторил свое предупреждение: византийцы должны заранее принять главенство папы на нем. Добившись от Алексея предложения присутствовать, папа получил от византийцев величайшую уступку, которую они сделали перед надвигающимся Четвертым крестовым походом.
Сделав предложение созвать церковный собор, Алексей III не стал ждать ответа, а осенью 1199 г. снова написал папе и потребовал, чтобы Иннокентий заставил Амальрика из Лузиньяна – короля Иерусалима и Кипра – возвратить последний его законному владельцу – Византии. Алексей предложил в ответ предоставить большие ежегодные субсидии королю и двум военным орденам в Палестине; но если ему будет отказано в этой просьбе, император пригрозил послать военно-морскую экспедицию на Кипр. Встревоженный этой угрозой, Иннокентий попытался умиротворить своего союзника мольбами и угрозами. Как он написал в своем письме в декабре 1199 г., Кипр принадлежал не Византии, когда Ричард Львиное Сердце завоевал его, а независимому правителю; если Алексей совершит на остров нападение, то Амальрику придется отвлечься от выполнения своей задачи – обороны Святой земли, от чего выиграют только неверные. По этой причине короли Западной Европы якобы написали ему, настоятельно убеждая его удержать Алексея от его плана, которому следует остеречься от потери расположения папы из-за пролития христианской крови. В то же время папа написал королям Франции и Англии, чтобы они сплотили общественное мнение против плана императора Алексея III. Он попросил их написать в Константинополь и отговорить Алексея от действий, наносящих вред интересам христианского мира, а также предложить ему в случае повиновения папе римскому, что они используют все свое влияние в курии на пользу Алексею. Однако император был занят решением более насущных проблем и не мог предпринять никаких действий против Кипра; он просто хотел посмотреть, как далеко зайдет папа, оказывая ему свою поддержку.