Poco dopo essi s'unirono al lombardo Ardoino, il quale servendo con loro nell'armata di Maniace, e mostrandosi valoroso soldato, fu non pertanto da quel generale di vilissimi schiavi che più non avevano sentimento d'onore, percosso col bastone in presenza delle sue truppe per cagione di un cavallo che gli si voleva rapire. I Normanni non fecero travedere la loro indignazione finchè non furono dai vascelli greci portati al di qua dello stretto: ma poichè trovaronsi sulle coste d'Italia, convennero di riunirsi in Aversa il giorno di Natale del 1041, chiamandovi ancora il lombardo Ardoino; il quale, soffiando nel cuor de' Normanni l'implacabile suo odio, li determinò ad attaccare le province dell'impero d'Oriente ed a conquistare per sè medesimi ciò che i Greci possedevano ancora nella Puglia e nella Calabria. Così ardita intrapresa veniva resa meno difficile da una rivoluzione, che avendo posto sul trono di Costantinopoli un nemico di Maniace, forzò questi a ribellarsi, e per tal modo a lasciar le province greche quasi senza difesa. I Normanni si assoggettarono a dodici capi scelti da loro, cui diedero il titolo di conti; affidando ad Ardoino il supremo comando della piccola loro armata, accresciuta di trecento uomini che gli diede Rainolfo conte d'Aversa. Avanzatisi nell'interno della Paglia, occuparono Melfi, che gli aprì le porte senza opporre veruna resistenza; presero in seguito Venosa, Ascoli e Lavello, ed in tre successive battaglie trionfarono tre volte dei Greci. Rinforzaronsi poi con nuove alleanze, e per ricompensarli de' ricevuti soccorsi, accordarono l'onore del comando a due altri capi Atenolfo ed Argiro; il primo de' quali, essendo fratello del duca di Benevento, gli aveva procurato il soccorso de' Lombardi, mentre Argiro, ricchissimo cittadino di Bari e figliuolo dell'illustre Melo, li favoreggiò col suo credito presso i Pugliesi e presso i partigiani che aveva suo padre nelle greche città. In questa guerra il valore e l'intrepidezza spesso appoggiate dall'astuzia e dall'intrigo stavano dal lato de' Normanni: i Greci all'opposto erano vili, disuniti, scoraggiati.