Papa Leone IX, vedendo la sua Benevento minacciata, tentò di contrastarne l'ascesa; ma l'esercito pontificio fu rovinosamente sconfitto nella battaglia di San Paolo di Civitate (1053), nella neonata contea di Puglia, il Papa fu catturato, e così Benevento rimase un'isola pontificia in terra normanna.
Nel 1059 Roberto il Guiscardo degli Altavilla strinse un patto con papa Niccolò II, il Concordato di Melfi, con cui si dichiarava formalmente suo vassallo, ottenendo in cambio i titoli (ancora solo nominali) di duca di Puglia (che comprendeva anche la Basilicata) e di Calabria (che era però ancora in parte in mano ai bizantini), parte della Campania e Sicilia (che era però ancora in mano agli Arabi). I Normanni riuscirono ben presto a cacciare dal Meridione la presenza bizantina con ripetute spedizioni che si conclusero con la conquista ad opera di Roberto il Guiscardo della città di Reggio Calabria, dove egli confermò il suo titolo di duca di Calabria. Gli Altavilla così poterono ben presto dedicarsi alla Sicilia.
La loro fortuna fu nell'avere dalla loro parte il papa, in cerca di alleanze durante la difficile disputa contro l'Impero tedesco. Il pontefice infatti, superata l'iniziale diffidenza e ostilità, aveva commesso l'ennesima infrazione formale rispetto a Bisanzio, legittimamente proprietaria dei territori italiani (altri smacchi del pontefice a Bisanzio erano stati, secoli addietro, le incoronazioni dei di Pipino il Breve e di Carlo Magno, arrogandosi diritti che poteva vantare solo sostanzialmente, ma non formalmente). Il papa in quell'occasione aveva comunque il pretesto della scisma d'Oriente, che gli diede l'opportunità per rivendicare a sé territori dell'imperatore eretico, sui quali quest'ultimo non era ormai più in grado di esercitare la propria autorità.
I Normanni divennero allora nemici dei bizantini, venendone espulsi dall'esercito (molti erano i mercenari), e Roberto il Guiscardo tentò oltretutto la conquista dell'Epiro, che non gli riuscì (1081-1085), nonostante un nuovo avallo papale.
Ruggero Bosso d'Altavilla, fratello di Roberto, alla testa di un folto gruppo di cavalieri nel 1061 sbarcò a Messina e invase l'isola (allora sotto dominio saraceno), riuscendo nel 1072 ad arrivare a Palermo, che venne poi eletta capitale. Mentre Boemondo I d'Antiochia, figlio della prima moglie di Roberto, diventava verso la fine del 1088 sovrano incontrastato del Principato di Taranto, Ruggero I insieme al figlio Ruggero II, formavano il Regno di Sicilia, creando così in Italia uno stato di dimensioni considerevoli: il Regno normanno di Sicilia.
Ruggero II, nominato re di Sicilia e duca di Puglia e di Calabria nella cattedrale di Palermo durante la notte di Natale del 1130, estese il dominio normanno in Italia meridionale con la conquista del Ducato di Napoli (1137) e, con le Assise di Ariano (1140), conferì al suo Regno un'organizzazione feudale rigidamente gerarchica e strettamente legata alla persona del sovrano. Il dominio dei Normanni nell'Italia meridionale ebbe termine tra il 1194 (morte di Tancredi di Lecce) e il 1198, quando Enrico VI di Svevia, Imperatore del Sacro Romano Impero (morto nel 1197), in virtù del suo matrimonio con Costanza d'Altavilla (morta nel 1198), unì alla corona imperiale quella di re di Sicilia.