Ivi riunì le sue truppe e trasportò ivi i tesori ch’erano nel real palazzo di Palermo. Avvicinatosi Arrigo alla capitale nel novembre nel 1194, per un’araldo intimò alla città d’arrendersi. I Palermitani, inabili a difendersi, risposero: essere pronti a riceverlo. Egli fatto precedere alcune schiere, entrò in città, circondato da molti baroni alemanni, avendo alla destra Filippo duca di Svevia, suo fratello. Non ebbero sulle prime i Siciliani ragione di dolersi di lui. La florida età sua e la bellezza della sua persona lo rendevano a tutti gradito; ed egli, mascherando i suoi veri sentimenti, si mostrava a tutti piacevole, nè facea travedere alcun mal’animo contro coloro, che avean parteggiato per Tancredi. Convocato il parlamento, vi fu riconosciuto re di Sicilia; poi nel duomo fu coronato dall’arcivescovo Bartolomeo Offamill, che era succeduto al fratello Gualtiero.
      Pur comechè avesse re Arrigo ottenuto con tanta facilità il regno, che da lung’ora affettava, non teneva sicuro il suo dominio in Sicilia, nè lo era, finchè non fosse nelle sue mani il piccolo Guglielmo III ed ogni avanzo della famiglia di Tancredi. Non era lieve il trarli di forza da Caltabellotta, sito tanto forte e ben munito; era anzi ben da temere che, mentre egli sprecava le sue forze sotto quelle mura, una conflagrazione generale divampasse nel regno. Per averli a man salva ricorse al tradimento. Già sin da che era entrato in Palermo, era venuto dicendo: sè non avere alcun rancore contro la famiglia di Tancredi; non avere impreso la conquista del regno per voglia d’offendere alcuno; ma per far valere i dritti incontrastabili della moglie.