In 871 heroverden de Byzantijnen de stad Bari, de hoofdstad van het emiraat Bari op de Saracenen. Ze stichtten er de ThemaLangobardia Minor met twee strategoi aan het bewind. Een van hen had als hoofdplaats Bari.
In 999 werd de strategos van Bari bevorderd tot Katapanos, of Patricius van Italië.
Vanaf 1017 had het Katapanaat te kampen met Noormannen, die als huurling van Lombardische steden in Apulië optraden. Vanaf 1030 kregen de Noormannen vaste voet aan de grond en begonnen met de verovering van Zuid-Italië. In 1040 was het grootste deel van Apulië verloren gegaan voor de Byzantijnen. In 1056 keerden zij nog eenmaal terug om Bari te belegeren.