После смерти последнего внука сицилийского монарха перед Генрихом открылась дорога к сицилийской короне. Однако местная аристократия не приняла немца и усадила на трон брата Констанции Танкреда.
Новости о выходке сицилийской знати и смерти отца в Третьем крестовом походе дошли до Генриха примерно в одно время. Недолго думая, он встал во главе армии и направился в Италию. Благодаря ловкости, с которой действовал Генрих, ему удалось быстро разрешить ссоры североитальянских вельмож и заручиться их поддержкой. В апреле 1191 г. он уже находился в Риме, где был коронован. Ну а потом настала очередь юга Италии, включая остров Сицилию. Но здесь удача отвернулась от Генриха: хорошо защищенный Неаполь успешно держал осаду, а установившаяся жара поспособствовала распространению в германской армии чумы. Генрих тоже плохо себя почувствовал и приказал отступать.
Между тем дела на родине требовали незамедлительного прибытия короля: сын Генриха Лева подбил людей на восстание. Расправиться с ним Генриху не составило труда, однако времени на это ушло немало.
В 1192 г. один из вассалов Генриха II задержал в Австрии английского короля Ричарда Львиное Сердце, который возвращался из Крестового похода. Поскольку он считался врагом германского монарха, то Генрих забрал пленника себе, попросил за него выкуп и потребовал у Ричарда, чтобы он признал себя вассалом германского императора. Лишь на этих условиях Ричарда отпустили.
Вскоре стало известно, что сицилийский король скончался, оставив корону своему несовершеннолетнему сыну. Генрих быстренько собрался и снова отбыл в Южную Италию, чтобы присоединить Сицилию к Германии. В этот раз поход удался на славу. В сицилийской столице, городе Толедо, в обмен на гарантии сохранения за ними владений королева Сибилла и ее сын отреклись от престола.