Il primo non erasi determinato a maritare Costanza che per assicurare l'ordine della successione e preservare il regno da una guerra civile; onde l'aveva dichiarata sua erede, facendo che i più principali baroni de' suoi stati le giurassero fedeltà. Ma i Siciliani vedevano con orrore trasferirsi in un principe straniero la sovranità della loro isola, quando eravi un principe normanno, di non legittimi natali bensì, ma per altro illustri. Era questi Tancredi conte di Lecce, figlio d'una contessa di Lecce e di Ruggiero figliuolo primogenito del primo re di Sicilia. Il di lui matrimonio non era stato legittimato dall'approvazione paterna, nè consacrato dalla Chiesa. Pure l'unione di questo principe con una dama d'alto rango, cui era stato fedele fino alla morte, non sembrava tale agli occhi de' Siciliani, che dovesse degradare il figliuolo e privarlo della sua eredità. Tancredi fu quindi chiamato a Palermo in principio del 1190 dalla nobiltà dei due regni e proclamato re277.
      Il primo pensiere d'Enrico dovette essere quello di riconquistare un regno che gli veniva tolto nell'istante in cui verificavasi il suo diritto alla successione. Per ricuperare l'eredità della sposa chiese ajuto alle repubbliche italiane e specialmente alle marittime. Ci furono conservate le parole stesse da lui dirette ai Genovesi quando pochi anni dopo bramava averli sussidiarj in una seconda spedizione: egli non faceva che ripetere le prime offerte. «Se dopo Dio, col vostro ajuto io posso ricuperare il mio regno di Sicilia, l'onore sarà mio, ma tutto vostro il profitto.