Establishing a stronghold at Monte Gargano in Apulia, they joined forces with the Lombard Melus of Bari, who had rebelled against his Byzantine overlords but who was currently on the run.
Their first major engagement with the army of the Byzantine catepan Basil Boioannes, fought at the Battle of Cannae, an ancient Apulian villa, was a disaster for the Normans and ended in defeat.
Rainulf, who now came to the fore as the undisputed leader, withdrew with the remnants of the band from Apulia to Campania, where, according to Amatus of Montecassino, though surrounded by enemies they were able to take advantage of dissension among the undisciplined Lombard lords.
[1] In 1034, this first wife died, and Rainulf married the daughter of the duke of Amalfi, who was also the niece of Sergius' inveterate enemy, Pandulf IV of Capua; He expanded his territory at the expense of the abbey of Montecassino.
He conquered his neighbour Pandulf's principality, and Conrad approved the union of the two domains, which formed the largest polity in southern Italy.
[5] In 1042, after the victory of his Norman ally William Iron Arm, he received, from the erstwhile Byzantine territories, suzerainty over Siponto and Monte Gargano.