Фридрих воспринимал собственные права и права своей семьи очень серьезно. На деле он был христианином вполне традиционных воззрений, полагавшим, что в качестве императора он должен быть вселенским монархом, божественным помазанником по византийской модели; поскольку же он — потомок нескольких поколений крестоносцев и наследник Карла Великого, то его миссия — освобождение Иерусалима. Он уже дважды принимал крест, но постоянно откладывал выступление в поход.
Теперь же, став королем Иерусалимским, Фридрих приступил к детальному планированию нового крестового похода — но, разумеется, в своем собственном стиле. Пообещав папе отправиться в крестовый поход, он отослал беременную жену в свой гарем в Палермо, однако 16-летняя Иоланта умерла, едва родив императору сына. Поскольку Фридрих получил титул короля Иерусалимского в результате династического брака, сын его не наследовал этот титул. Однако император не собирался допускать, чтобы эта малозначительная деталь как-то повлияла на его новый подход к стратегии крестовых походов.
Император надеялся получить Иерусалим, используя соперничество наследников Саладина. И действительно, султан Камиль предложил ему Иерусалим в обмен на помощь в борьбе против Муаззама, удерживавшего город. В 1227 году Фридрих наконец выступил, но заболел в дороге и вернулся назад. Папа Григорий IX предал его за это анафеме, что для крестоносца было, конечно, большим неудобством. Фридрих приказал своим тевтонским рыцарям и пехоте двигаться вперед, но к тому времени, когда он в сентябре 1228 года присоединился к ним в Акре, Муаззам уже умер, а Камиль занял всю Палестину — и отозвал свое предложение.
Однако теперь ему предстояло сражаться и с сыновьями Муаззама, и с Фридрихом. Война на два фронта была не по силам Камилю. Но императору тоже не хватало сил, чтобы взять Иерусалим, и он вступил в тайные переговоры с султаном.
Камиль был столь же необычным человеком, что и Фридрих. В свое время юного сына Саладина посвятил в рыцари сам Ричард Львиное Сердце. Ведя переговоры о разделе Иерусалима, император и султан попутно обсуждали философию Аристотеля и арабскую геометрию. «У меня нет действительного желания владеть Иерусалимом, — признавался Фридрих посланцу Камиля. — Я всего лишь хочу сохранить мою честь в глазах христиан». У мусульман иногда складывалось впечатление, будто христианство для императора — «всего лишь игра». Султан прислал Фридриху девочек-танцовщиц, а император развлекал своих мусульманских гостей танцами девочек-христианок. Патриарх Герольд объявил певичек и жонглеров Фридриха «не только порочными, но и не достойными называться христианами». В перерывах между переговорами Фридрих ездил на соколиную охоту и соблазнял все новых дам; изображая из себя трубадура, он писал одной из них: «Ах, я и не представлял, сколь тягостной будет для меня разлука с моей дамой. Мне не забыть сладостные мгновения нашего общения. Счастливая песнь, лети к прекрасному цветку Сирии, к той, что сердце мое украла и не возвращает. Попроси эту самую возлюбленную из женщин вспомнить о своем верном слуге, который будет страдать от любви к ней, пока не сделает все, что ей будет угодно».
Когда переговоры зашли в тупик, Фридрих с войском двинулся вдоль побережья до Яффо, повторяя путь Ричарда и явно угрожая Иерусалиму. Эта военная хитрость сделала свое дело: 11 февраля 1229 года он получил то, что многим и в самых смелых мечтах казалось невозможным. В обмен на десятилетнее перемирие Камиль уступал Фридриху Иерусалим, Вифлеем и коридор к морю. Иерусалимские мусульмане под началом своего кади сохранили за собой Храмовую гору, возможность свободно подниматься на нее и молиться. Этот договор о совместном суверенитете совершенно игнорировал евреев (которые по большей части бежали из города), однако он и по сей день остается самым дерзким мировым соглашением в истории Иерусалима.
Оба мира — и христианский, и мусульманский — были потрясены. В Дамаске сын Муаззама Насир Дауд объявил день всеобщей скорби. Толпы людей рыдали над горестными новостями. Камиль настаивал: «Мы уступили лишь несколько церквей и разрушенных зданий. Святые места и почитаемая Скала остаются в наших руках». Договор был ему на пользу: Камиль сумел воссоединить империю Саладина под своей властью. Что же до Фридриха, то патриарх Герольд запретил ему, как отлученному от церкви, входить в Иерусалим, а тамплиеры осудили императора за то, что он не отстоял Храмовую гору.
В субботу 17 марта Фридрих в сопровождении своих арабских телохранителей и пажей, германских и итальянских воинов, тевтонских рыцарей и двух английских епископов подъехал к Яффским воротам. Его встречал представитель султана Шамс аль-Дин, кади Наблуса, который вручил императору ключи от Иерусалима.