Od 873 miasto znajdowało się pod panowaniem Bizancjum (zostało odbite z rąk Saracenów). Około 965 stratēgos miasta Bari (tytuł odpowiadający rangą dzisiejszym generałom lub admirałom) otrzymali tytuł katepano Italii, połączony z urzędniczym tytułem patrikios, który odpowiadał hierarchicznie mniej więcej rzymskiej godności prokonsula. Stopień wojskowy i urzędniczy katepanō oznaczał w języku greckim „najważniejszy”. W kwietniu 1071 Cesarstwo Bizantyńskie utraciło kontrolę nad Bari, co ostatecznie położyło kres zarówno Katepanatowi Italii (historyczna prowincja Cesarstwa Bizantyńskiego w południowej części Półwyspu Apenińskiego), jak również bizantyńskiemu panowaniu w Italii.
W wiekach XI-XIII miasto było punktem zbornym rycerzy chrześcijańskich biorących udział w wyprawach krzyżowych i w tym czasie przekształciło się w zamożną republikę czerpiącą swe bogactwa z handlu morskiego. W XIII w. cesarz i król Sycylii Fryderyk II rozbudował system obronny miasta, m.in. normandzki zamek i bastion portowy. Następnie było stolicą samodzielnego księstwa Bari należącego do rodu Sforzów, z którego pochodziła żona Zygmunta I Starego – królowa Bona.