Наконец, незадолго до смерти, Андроник заключил формальный союз с султаном Египта Саладином. По словам западного хрониста, “движимый болью и огорчением [Андроник] должен был прибегнуть к совету и поддержке Саладина.”[175] Условия этого союза, скрепленного клятвой, звучат следующим образом. Если Саладин сможет с помощью советов и помощи императора захватить Иерусалим, Саладин оставит для себя любую другую область, которую они* смогут завоевать. Иерусалим и все побережье, кроме Аскалона, остаются свободными. Однако он будет владеть этими территориями под сюзеренитетом Андроника. Император будет владеть всеми завоеванными у Иконийского султана территориями до Антиохии и Малой Армении, если новые союзники смогут ими овладеть. Однако “вследствие своей смерти, Андроник не смог реализовать этот план.”[176] Договор этот показывает, что Андроник был готов уступить Палестину Саладину на условии, что тот признает сюзеренитет империи. Однако ни соглашение с Венецией, ни уступки папе, ни союз со знаменитым Саладином не могли спасти ситуацию, или сохранить власть в руках Андроника.

          В восточной части Средиземноморья наместник острова Кипр Исаак Комнин отделился от империи и провозгласил независимость острова под своим правлением. Не имея хорошего флота, Андроник не смог подавить восстание. Кипр был потерян. Потеря Кипра была серьезным ударом для империи, так как она имела там важный стратегический и торговый пункт, приносивший казне большие доходы, особенно благодаря торговле с латинскими государствами на Востоке.