Molti sono coloro che si offrirebbero come tutori del piccolo orfano, e non certo per carità cristiana. I più interessati sono i nobili tedeschi, già scesi in Sicilia al seguito di Enrico VI. Ma anche il papa, Innocenzo III, grande fautore della superiorità della Chiesa su ogni potere secolare, mostra interesse per l’educazione del piccolo Federico.
Costanza, troppo lontana culturalmente dai rozzi baroni germanici, sceglie l’alleanza con il pontefice. E con la sua preziosa benedizione, un bimbo di nemmeno 4 anni viene incoronato re di Sicilia nel Duomo di Palermo: è il giorno di Pentecoste del 1198. È l’ultimo atto politico di Costanza che muore pochi mesi dopo. Innocenzo, del quale il re di Sicilia è vassallo, nomina un collegio di vescovi quali reggenti in attesa della maggiore età del piccolo monarca.
A Palermo Federico vive una triste infanzia quasi prigioniero nel castello di Maredolce. La leggenda vuole che il re bambino sfugga, di tanto in tanto, ai suoi tutori per scorrazzare con i monelli nelle strade della città. Il contatto con l’ambiente palermitano, caratterizzato dalla coesistenza di tre culture, l’occidentale cristiana, la bizantina e l’araba, sarà decisivo nella formazione di Federico.
In un clima reso fosco dai continui intrighi e dalle lotte che lo vedono pedina inerme nelle mani dei potenti, Federico diventa direttamente adulto. A quattordici anni viene proclamato maggiorenne. Otto mesi dopo sposa Costanza, figlia del re d’Aragona, vedova ventiquattrenne del re d’Ungheria.