Era convinto, però, che instaurare un dominio stabile in Palestina fosse impossibile e, invece di combattere contro i musulmani, cercò di dialogare con loro. Trattò, così, con il sultano d’Egitto e ottenne pacificamente da lui il ritorno di Gerusalemme sotto il controllo cristiano, concordando una tregua di dieci anni. L’accordo di Federico con gli “infedeli” suscitò scandalo e proteste e gli inimicò ancora di più il papa.