Auf der Synode von Melfi (1059) belehnte Papst Nikolaus II. den Grafen von Aversa, Richard I. Quarrel (1050-1078), mit dem lehnsrechtlich dem Kaiser unterstehenden Fürstentum Capua, das der Normanne 1058 erobert hatte. Gleichzeitig erteilte er Robert Guiscard, der die Nachfolge seines Halbbruders Humfried (+ 1057) als Graf von Apulien angetreten hatte, die Investitur in das Herzogtum "von Apulien, Kalabrien und künftig, mit Hilfe Gottes und des heiligen Petrus, von Sizilien". Woher er das Recht dazu nahnm, erklärte der Papst nicht. Die päpstlich-normannische Allianz war indes nicht nur eine Folge der Schlacht von Civitate, sondern auch eine indirekte Konsequenz der wenige Monate vorher abgehaltenen Lateransynode. Es war vorherzusehen, dass die Beschlüsse über die Papstwahl und die Laieninvestitur eine negative Reaktion des römischen Adels und des Kaisers hervorrufen würden. Für die Normannen war die Belehnung durch das Papsttum ein großer Erfolg; ihr Ansehen stieg, und ihre Eroberungen erhielten eine neue Legitimierung.
Als Roger I. um 1055 in den Süden kam, half er Robert Guiscard bei der Niederschlagung eines Aufstandes. Bald entstanden jedoch Konflikte zwischen den beiden Brüdern. Roger wollte sich in Kalabrien einen eigenen Herrschaftsbereich aufbauen, womit sein Bruder nicht einverstanden war. Ebenso wie Apulien hatte Kalabrien bisher zum Byzantinischen Reich gehört. Die einheimische Bevölkerung versuchte aus der Uneinigkeit der Normannen Nutzen zu ziehen und sie zu vertreiben. Robert Guiscard war also gezwungen, sich mit seinem Bruder zu verständigen und trat ihm die Hälfte Kalabriens ab. Gemeinsam gelang es den Brüdern, ihre Herrschaft zu festigen.
Nach der Einnahme Palermos einigten sich die Brüder über die Aufteilung Siziliens, das allerdings erst zur Hälfte erobert war. Robert Guiscard hatte aufgrund seiner Stellung als Herzog von Apulien, Kalabrien und Sizilien formal die Herrschaft über die ganze Insel, wo aber in Wirklichkeit Roger I. recht frei schalten und walten konnte. Ähnlich wie in Kalabrien behielt der Herzog die Hälfte der wichtigsten bisher gemachten Eroberungen (Palermo, Messina und Val Demone) in seinem Besitz. Ende 1072 verließ er die Insel, die er nicht mehr wiedersehen sollte. In Apulien waren Aufstände normannischer Adeliger niederzuschlagen. In den folgenden Jahren wurde Robert Guiscard von anderen Projekten in Anspruch genommen. HEINRICH IV. bot ihm 1076 die Herzogsinvestitur aus eigener Hand an, was der Normanne aber ablehnte. Als Vasall des Papstes hatte er größere Handlungsfreiheit, denn Gregor VII. war auf seine Waffenhilfe angewiesen. 1077 gelang Robert die Unterwerfung Salernos, des letzten langobardischen Fürstentums in S-Italien. Sein Hauptinteresse war aber auf Byzanz gerichtet, von dessen Eroberung er träumte. Auf einem Feldzug gegen das oströmische Kaiserreich fand er dann 1085 den Tod.