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