最终，受绝罚者所率的第六次十字军，从意大利南部最大的海港布林迪西出发了。这一天是1228年6月28日，33岁的腓特烈为出征做了周密的准备。
腓特烈所率的舰队包括40艘桨帆船和上百艘运输帆船，上面装有大量军粮、武器和马匹，还乘坐着来自西西里和意大利南部的100名骑兵和3000名步兵。以上只是皇帝亲自指挥出征的部队，还有一部分人马已经提前出发。
先行出发的是在瘟疫爆发前一年，由条顿骑士团团长赫尔曼率领的800名德意志骑士。这支部队除了骑士，还包括一部分步兵和后勤人员，总人数大约是骑士人数的三倍。
先行部队在1227年秋天到达了巴勒斯坦。他们遵照腓特烈的命令，在西顿港进行整备，并完成了对港口防御工事的改造。
条顿骑士团的骑士接下来对阿克和蒙福特的城堡进行了加固，到1228年，他们又前往凯撒利亚，改造当地的防御工事。这一系列工作都是为了确保腓特烈二世登陆时军队的安全和拥有足够数量的前线防御基地。
将参加第六次十字军的全部人马合计起来，包括900—1000名骑兵，以及三四千名步兵。兵力并不众多。
但这支军队的指挥完全处在腓特烈二世一个人支配下。直接听命于他的两位总指挥，分别是陆上的条顿骑士团团长赫尔曼，和海上的马耳他的恩里科。两人都是能征善战的武将。当腓特烈到达巴勒斯坦以后，他还与圣殿骑士团和医院骑士团并肩作战，加上条顿骑士团的支持，协调一致。
年届50的条顿骑士团团长赫尔曼，对比自己年轻15岁的神圣罗马帝国皇帝始终保持着绝对的忠诚。他不仅作为一名战将，也作为腓特烈二世的外交人员活跃在皇帝身边，时刻代表皇帝的立场。
如果说赫尔曼是腓特烈的右臂，皇帝的左臂就是活跃的海军统帅恩里科了。马耳他一直是基督教世界抵抗穆斯林的最前线。这位出身马耳他的将领，就是最忠实执行皇帝命令的人物了。与赫尔曼一样，恩里科也善于外交活动，是腓特烈身边不可多得的人才。
恩里科虽然不如赫尔曼年龄大，但与34岁的腓特烈相比，还是要年长不少。
他们两人就成为了腓特烈事实上的副将。因此，有两人辅佐的第六次十字军，规模不大，却都是精兵强将。
除此以外，第六次十字军还有一大特色。
这就是本次十字军的海军力量完全是由自己控制的。回顾第三次十字军，法国国王腓力需要完全依赖热那亚的海军力量，而英国狮心王理查虽然动用本国舰队运输兵士，在海战时也不得不依赖比萨和热那亚的力量。英格兰的帆船适于运输，但在海战时，可靠的战舰还是依赖桨橹灵活机动的桨帆船。适于地中海航行的桨帆船并非欧洲北部各民族常用的船只，只有习惯于在地中海活动的当地船员善于驾驶。
腓特烈二世的领地南意大利和西西里，都面对着地中海。这些地区的海员不仅长于海运，还是真正意义上的桨帆船驾驭者。无论是赫尔曼先期率领的骑士团所乘坐的20艘桨帆船，还是腓特烈自己率领的40艘桨帆船，都是在意大利南部和西西里岛建造的。
这些舰船的总指挥，正是生长于马耳他，熟悉整个地中海的恩里科。因此，拥有自身的海军力量而无须他国提供，对于指挥作战来说是殊为有利的。腓特烈的海军也因此独具特色。
腓特烈的舰队中还包括为本次东征特制的运输船。这种船的底部很浅，可以溯尼罗河而上，进攻开罗。
腓特烈二世以周密的准备前往东方。虽然他还没有与阿尔·卡米尔交战的经历，但他已经具备了充分的战斗力。作为最高司令官的腓特烈，还从没有在此前的作战中失利过。而此时皇帝的打算，是在并不动用自己军事力量的情况下，和平达到东征的战略目标。
6月28日离开布林迪西的舰队，沿着希腊半岛的西侧南下，然后转舵向东，经过克里特岛和罗得岛，于7月21日在塞浦路斯岛南部的利马索尔港登陆。经过3周的旅行后，腓特烈一行于塞浦路斯岛上休整6周。与狮心王理查一样，腓特烈二世也十分重视塞浦路斯岛的战略地位。
从理查时代转入天主教徒控制的塞浦路斯岛，正由一位8岁的幼年国王统治着。而以贝鲁特为中心发展自己势力的伊柏兰家的继承人约翰，正对塞浦路斯虎视眈眈。准备君临巴勒斯坦的腓特烈，自然不希望塞浦路斯在自己的眼皮底下发生内乱。况且塞浦路斯还是能为自己提供大量军粮的基地。
腓特烈二世的进军路线
腓特烈非常希望不动用军事力量就能解决塞浦路斯的问题。但是，腓特烈和约翰的谈判并没有进展下去，皇帝也没有派兵追击从法马古斯塔逃出的约翰，而是最终与伊柏兰家签订了协议。
双方的协议包括如下内容：
一、直到问题完全解决，皇帝承认伊柏兰家的约翰对贝鲁特的领主权；
二、皇帝到达巴勒斯坦之后，若开展军事行动，约翰负有保卫叙利亚基督徒的责任；
三、这期间塞浦路斯王国的防务，由腓特烈的部众代替幼年国王完成。
从此塞浦路斯的问题得以解决，腓特烈也于9月3日出发。9月7日，大军在巴勒斯坦基督教势力的中心阿克登陆了。
十字军史上神圣罗马帝国皇帝首次驾临圣地，引爆了中近东基督徒的宗教狂热。除了阿克的居民，邻近各个城市的基督徒都蜂拥而至，将阿克城的港口围了个水泄不通，期待着皇帝御驾的光临。
沐浴着秋季阳光的腓特烈二世，在以阿克大主教为首的一众要人引导下，从港口向王宫缓缓行进。英姿勃发的皇帝跨坐在马上，俨然一副中近东全体基督徒保护者的威严形象。
自上而下的全方位热烈欢迎，使腓特烈感到风光无限。同行的巴里大主教将到达的盛况记录下来，写成书信，委托恩里科派人呈送教皇格列高利九世。大主教十分期待教皇能够收回成命，解除对皇帝的绝罚。
就在这时，两位手持教皇敕令的修士，乘船来到了阿克。他们一登陆，便径直前往中近东基督徒的最高精神领袖——耶路撒冷牧首的官邸，将教皇的敕令递交给牧首。
在敕令中，教皇重申了第二次绝罚的告示：基督徒没有服从已受绝罚的皇帝的义务。教皇特别明令禁止宗教骑士团服从皇帝的调遣，严禁骑士团团员与皇帝并肩作战。
得知教皇的敕令，阿克的居民动摇了。但他们毕竟亲眼目睹了皇帝的飒爽英姿，一时间难以接受绝罚的事实。最终，阿克城内居民分裂为敌视皇帝的一方和支持皇帝的一方。
而在各个宗教骑士团的内部，人们为是否接受皇帝、听从教皇展开了激烈的争论。圣殿骑士团和医院骑士团与其他修会一样，都处于罗马教皇直接管辖下。理应服从教皇命令的两大骑士团，由于在中东的长期驻扎，对叙利亚、巴勒斯坦一带基督徒的现状十分清楚。
一番争论之后，两大骑士团达成了一致，都决定支持腓特烈的十字军。他们也分别致信教皇，禀报了自己不得已的苦衷。
“在现在的条件之下，我们只得与皇帝并肩作战。但我辈的协助，绝非在皇帝名义下，而是为了上帝和全体基督徒尽全力。”
同样是宗教骑士团的条顿骑士团就没有以上的困扰了。条顿骑士团的成员仅限于德意志贵族出身者，并不直接受罗马教皇管辖，因此天然服从皇帝的命令。
出于政治上避免自己处于风口浪尖的考虑，腓特烈将第六次十字军名义上的总统帅职务交给了条顿骑士团的团长赫尔曼。
这样一来，第六次十字军就不再是受绝罚的皇帝领导了，而是名正言顺地由条顿骑士团团长来率领。