Following the fall of the Exarchate of Ravenna in 751, Byzantium had been absent from the affairs of southern Italy for almost a century, but the accession of Basil I (reigned 867–886) to the throne of Constantinople changed this: from 868 on, the imperial fleet and Byzantine diplomats were employed in an effort to secure the Adriatic Sea from Saracen raids, re-establish Byzantine dominance over Dalmatia, and extend Byzantine control once more over parts of Italy. As a result of these efforts, Otranto was taken from the Saracens in 873, and Bari, captured from Arabs by the Holy Roman Emperor Louis II in 871, passed under Byzantine control in 876. The expeditions of the capable general Nikephoros Phokas the Elder in the mid-880s further extended Byzantine control over most of Apulia and Calabria. These victories were followed up by his successors and laid the foundation of a resurgence of Byzantine power in southern Italy, culminating in the establishment of the theme of Longobardia in c. 892. The regions of Apulia, Calabria and Basilicata would remain firmly under Byzantine control until the 11th century. In c. 965, a new theme, that of Lucania, was established, and the stratēgos (military governor) of Bari was raised to the title of katepanō of Italy, usually with the rank of patrikios. The title of katepanō meant "the uppermost" in Greek. This elevation was deemed militarily necessary after the final loss of nearby Sicily, a previously Byzantine possession, to the Arabs.
Some Norman adventurers, on pilgrimage to Monte Sant'Angelo sul Gargano, lent their swords in 1017 to the Lombard cities of Apulia against the Byzantines. From 1016 to 1030 the Normans were pure mercenaries, serving either Byzantine or Lombard, and then Duke Sergius IV of Naples, by installing their leader Ranulf Drengot in the fortress of Aversa in 1030, gave them their first foothold, and they began an organized conquest of the land. In 1030 there arrived William and Drogo, the two eldest sons of Tancred of Hauteville, a petty noble of Coutances in Normandy. The two joined in the organized attempt to wrest Apulia from the Byzantines, who had lost most of that province by 1040. Bari was captured by the Normans in April 1071, and Byzantine authority was finally terminated in Italy, five centuries after the conquests of Justinian I. The Byzantines returned briefly to besiege Bari in 1156.
The title Catapan of Apulia and Campania was revived briefly in 1166 for Gilbert, Count of Gravina, the cousin of the queen regent Margaret of Navarre. In 1167, with his authority as catapan, Gilbert forced German troops out of the Campania and compelled Frederick Barbarossa to raise the siege of Ancona.