Per il Puer Apuliae, l’area di Lucera era strategicamente rilevante a livello militare, economico e politico. Intorno al 1220-1223, in seguito a delle insurrezioni musulmane in Sicilia, l’imperatore decise di spostare gran parte della popolazione islamica (circa 20mila sudditi) fuori dall’isola.
Dato che Lucera fu una delle principali zone di insediamento, si rese necessario costruire un Palatium da cui controllare il nuovo e difficile contesto. La sua edificazione iniziò intorno al 1233 sul Monte Albano, zona abitata fin dal neolitico e sede dell’antica acropoli romana della città. Dopo la sconfitta degli Svevi, la cui potenza venne definitivamente distrutta da Carlo I d’Angiò nella Battaglia di Tagliacozzo del 1268, l’elegante e solenne complesso a base quadrata di tre piani venne sensibilmente modificato dagli Angioini e trasformato in una fortezza, cinta da mura, 22 torri e fossato.
Dell’originario palazzo federiciano, comunque, sono ancora visibili la “galleria dei tiratori”, ossia delle saettiere aperte su un muro a falsa scarpa, le volte a crociera e il cortile con fontana centrale.