W 1057 po śmierci brata Onufrego, który po zamordowanym Drago został przywódcą Normanów w Italii, Robert wyrósł na lidera normańskich wojowników w południowych Włoszech, którzy już otwarcie dążyli do opanowania tej krainy. W 1058 Robert osadził swojego młodszego brata Rogera na książęcym tronie w Kalabrii. W 1059 wszedł w przymierze z papieżem Mikołajem II i na synodzie w Melfi ogłosił się wasalem papieża oraz zobowiązał się przestrzegać zasad soborowych, za co otrzymał tytuł księcia wraz z inwestyturą Apulii, Kalabrii i Sycylii. W następnych latach Robert zajął Reggio i Brindisi, by w 1071 po trzyletnim oblężeniu zdobyć Bari, stolicę bizantyjskiej Italii. W tym samym czasie Roger podbijał Sycylię, która po zdobyciu Palermo wpadła w ręce Normanów, a Roger ogłosił się wasalem Roberta.
Następne lata upłynęły Robertowi na konsolidowaniu wszystkich zdobytych ziem. Do 1073 zmusił do uległości wszystkich normańskich buntowników. W tym czasie został ekskomunikowany przez papieża Grzegorza VII, który w ten sposób chronił papieskie włości w południowej Italii. Jednak, gdy po kolejnym buncie Robert stał się jeszcze silniejszy (władał całym Południem bez Kapui i Neapolu), a papież miał kłopoty z intrygami cesarza Henryka IV, Grzegorz VII poszedł w 1080 na ugodę.