На руку Фридриху было то, что султан аль-Камил сам был в тяжелом положении. Союз трех братьев Айюбидов, аль-Камила Египетского, аль-Муаззама Сирийского и аль-Ашрафа Джазирского, обеспечивший победу над Пятым крестовым походом, все более распадался. Между аль-Камилом и аль-Муаззамом Дамасским дело дошло до военных столкновений. Аль-Муаззам обратился за помощью к Джелал ад-Дину, сыну умершего хорезмшаха Мухаммеда, и признал его ленное верховенство. Выгнанный монголами из своего государства, Джелал ад-Дин с хорезмийцами отступил на запад и в 1224 г. основал новое государство в Ираке, Азербайджане и Большой Армении. В 1225 г. Джелал ад-Дин получил верховенство над Багдадом и халифом. Напуганный аль-Камил осенью 1226 г. послал к Фридриху на Сицилию своего эмира Факр ад-Дина просить императора о помощи от хорезмийцев. Взамен он повторил предложение 1219 г., обещав императору возврат завоеваний Салах ад-Дина, включая Иерусалим. Фридрих приветливо встретил эмира, но ничего не обещал. Для продолжения переговоров император направил с подарками и дружеским посланием епископа Палермо, который вместе с присоединившимся к нему в Акре регентом королевства Иерусалим Томмазо Ацеррским прибыл к султану в Каир. В Каире выяснилось, что Иерусалим с палестинскими землями принадлежит аль-Муаззаму. Епископ Палермо отправился в Дамаск к аль-Муаззаму за подтверждением. Аль-Муаззам теперь враждовал с аль-Камилом и гневно указал епископу на дверь, заявив, что, пока у него в руках сабля, никакого Иерусалима христиане не получат. Аль-Камил снова отправил Факр ад-Дина в королевство Сицилия поторопить Фридриха с походом. Император и эмир стали друзьями, Фридрих посвятил Факр ад-Дина в рыцари и разрешил носить на знамени свой герб — одноглавого орла.
Смерть аль-Муаззама в ноябре 1227 г. облегчила положение аль-Камила. Новым правителем Дамаска стал сын аль-Муаззама, 21-летний ан-Насир Дауд, человек умный и изворотливый. Аль-Камил немедленно двинулся в Палестину и осадил Иерусалим и Наблус. Ан-Насир обратился за помощью к другому своему дяде, аль-Ашрафу Джазирскому. Братья встретились недалеко от Газы и решили поделить земли племянника, как они объяснили, «в интересах ислама, чтобы защитить Палестину от франков». Аль-Ашраф пытался вероломно захватить в плен ан-Насира, но тот бежал в Дамаск. В конце 1228 г. братья осадили Дамаск, а ан-Насир обратился за помощью к Джелал ад-Дину.
Фридрих сразу известил султана о своем прибытии. Опасаясь Фридриха, который мог переметнуться на сторону ан-Насира, аль-Камил отправил к императору Факр ад-Дина, дав ему распоряжение вести переговоры как можно дольше, пока не падет Дамаск или Фридрих не уедет домой. Султан возлагал большие надежды на неблагоприятное положение императора из-за его раздора с церковью. Войны не хотели оба, но оба не могли уронить престиж в глазах своих единоверцев. Чтобы усилить переговорную позицию, Фридрих собрал все войска, какие мог, и двинулся в более чем стокилометровый поход по берегу моря на юг к Яффе. Магистр тамплиеров отказался сопровождать отлученного императора, и тамплиеров возглавлял палестинский прецептор (руководитель орденской провинции). Плохие отношения с тамплиерами у императора были еще со времени подавления восстания южноитальянских баронов в начале 1220-х гг., когда орден укрывал их от него в своих замках. В течение зимы 1228-1229 гг. Фридрих восстанавливал разрушенные укрепления Яффы, создавая плацдарм для наступления на Иерусалим.
Одновременно продолжались переговоры. Когда Фридрих потребовал возвращения всей Палестины, Факр ад-Дин сказал, что его господин не может так сильно обидеть мусульман. На это Фридрих сообщил по секрету своему другу-эмиру, что он лично обошелся бы без Иерусалима, но город нужен ему как преимущество в борьбе с папой. Для обеих сторон Священный город был разменной монетой.