Поразительное возвышение могущества Штауфенов со времени победы над норманнами, которое удивило весь мир, повлияло также на мелкие христианские владения на Востоке. Там уже в 1190 году Боэмунд III антиохийский дал ленную присягу герцогу Фридриху Швабскому, как заместителю императора, и то же самое собирались теперь сделать князья Армении и Кипра. В 1194 году Лев II отправил посольство в Рим и к немецкому императору, чтобы высшие авторитеты римского христианства украсили его королевство титулом. Папа Целистин III дружелюбно принял послов в надежде, что с этого времени он может подчинить своему главенству армянскую церковь, и дал им с собой освященную золотую корону для Льва. Генрих дал свое согласие на возвышение сана армянского правителя и обещал сам короновать князя, как только придет на Восток с предполагаемым крестовым походом. На Кипре господствовал в то время Гвидо, прежний король Иерусалимский. Тем временем он старался заманчивыми щедрыми предложениями побудить франкских рыцарей и граждан к поселению на острове, и имел в этом быстрый успех, так как в то время на сирийском берегу жило достаточно неимущих людей. Но хотя он теперь снова занял довольно видное положение, он назывался уже не королем, а только владетелем Кипра. В апреле 1195 года ему наследовал в правлении его младший брат, Амальрих Лузиньянский, а этот последний тотчас же послал двух знатных послов к Целестину и к Генриху как для того, чтобы устроить на острове римско-католическое епископство (в Никозии) с тремя суффраганами епископами, так и для того, чтобы сделаться вассалом империи и затем королем. Папа устроил церковные дела Кипра по желанию Амальриха, и Генрих VI милостиво принял ленную присягу своего нового вассала, послал ему, как знак пожалования лена, золотой скипетр и также обещал со временем лично венчать его королем.
Между тем уже начались приготовления к новому крестовому походу, «немецкому крестовому походу». 31 мая 1195 г. молодой император принял в Бари крест, после того как он уже перед тем установил крестовые проповеди и объявил, что он в продолжение целого года будет содержать в Святой земле 1500 рыцарей и столько же слуг, каждый рыцарь при отплытии должен был получить плату в 30 унций золота и необходимое продовольствие. В июне Генрих отправился в Германию и старался там собственным вмешательством возбудить рвение к священной войне, но достиг цели своих желаний не так скоро, как, вероятно, ожидал. То ему мешали болезни, которым он был часто подвержен при слабом здоровье, то успеху предприятия вредил раздор, который вспыхнул между ним и папой. Дело в том, что Целестин III сначала с горячей радостью приветствовал решение короля и поручил многим кардиналам объехать немецкие земли с крестовой проповедью, но с течением времени он пришел к заключению, без сомнения, что если странствие ко Святым местам будет успешно, то оно чрезвычайно оживит могущество Штауфенов и этим нанесет вред римской церкви, которую Штауфены и без того очень тяжело стеснили. Между тем, несмотря на возникшие отсюда противодействия, твердая воля Генриха все-таки мало-помалу достигла великого успеха. С осени 1195 года до весны 1196 г. было устроено несколько имперских сеймов, причем и в высших и в низших кругах оказалось столько же пылкое одушевление к освобождению Иерусалима, как во времена Готфрида Бульонского и императора Фридриха. Самым решительным был Вормский сейм в декабре 1195 г., когда Генрих сам каждый день присутствовал в соборе, чтобы возбуждать присутствующих к принятию крестового обета, и когда вокруг него с бурным восторгом теснилось дворянство и народ, как некогда около его отца на Майнцском «придворном сейме Христа». Первые отряды пилигримов отправились зимой с 1196 на 1197 год на юг в Апулию, где уже для них были готовы продовольствие и корабли; уже в марте 30 кораблей отплыли оттуда в Сирию. Вскоре после того на берегах Апулии собрались новые толпы, в целом до 60000 человек; а флот в 44 корабля, занятый многими тысячами нижненемецких пилигримов, обогнув западную Европу, уже дрался с мусульманами на португальском берегу и теперь вступил в Мессинскую гавань. В начале сентября вся армада под управлением императорского канцлера Конрада вышла в море; но сам Генрих VI остался в норманнском государстве, удержанный домашними делами. Главная часть флота отплыла прямо в Сирию и прибыла в Аккон 22 сентября. Канцлер направился сперва вместе с некоторыми немецкими князьями в Кипр, там по поручению Генриха он с большой пышностью короновал Амальриха Лузиньянского, а затем также поспешил в Аккон.