The Normans arrived in southern Italy around the millennium, and plunged into the political turmoil existing there. The Byzantines were the colonial power, pitted against various princedoms and city-states. The Normans began as mercenaries, often fighting on both sides in battles, but soon started to accumulate fiefdoms as reward for their service, thereby emerging as powerful independent players. They defeated the Byzantines in five successive battles in 1041 (receiving twelve baronies from the Prince of Salerno as reward), and in 1053 Humphrey of Hauteville destroyed the combined armies of the papacy and Holy Roman Empire at the Battle of Civitate, imprisoning Pope Leo IX. Now in command, they picked off Taranto (1064) and Bari (1071) in Apulia, and old an ally, Salerno (1076). The Byzantines were left with just a toehold in Naples. Turning to Fatimid-controlled Sicily, an early invasion was repulsed by an ‘infestation of tarantulas’, but they completed their conquest in 1091.