Henryk VI usiłował wtedy przekonać papieża do tego, aby udzielił Fryderykowi II, elektowi w Niemczech i dziedzicowi na Sycylii, chrztu i namaszczenia królewskiego. Celestyn, uparcie sprzeciwiający się unii niemiecko-sycylijskiej, odmawiał. Ostatecznie Henryk miał zaoferować papieżowi układ, zgodnie z którym Państwo Kościelne wróciłoby pod bezpośrednią władzę cesarza, a papież otrzymywałby od Cesarstwa stałą i wysoką daninę.
Ku absolutyzmowi thumb|Sarkofag Henryka VI w Palermo Jeszcze w 1196 Henryk wyjechał z Rzymu na Sycylię. W Kapui zwołał radę nadworną, przeprowadził okrutne represje wobec dawnych przeciwników i wprowadził stały i powszechny podatek. W 1197 na radzie w Palermo nakazał lustrację dokumentów królewskich z poprzednich lat. Baronowie sycylijscy wyczuwali zamysł Henryka, aby cofnąć donacje i przywileje jego poprzedników. Zawiązał się przeciw niemu spisek, dążący do osadzenia na tronie jednego z miejscowych dygnitarzy. Został jednak wykryty, po czym niemieckie wojsko Henryka, stacjonujące we Włoszech z zamiarem wyruszenia przeciw Turkom, pokonało opozycjonistów w bitwie pod Katanią. Przeprowadzono pokazowe, niezwykle okrutne egzekucje spiskowców. W związku z komplikacją sytuacji na Sycylii cesarz nie wziął udziału w wyprawie, którą wyprawił do Ziemi Świętej.