La dominazione bizantina avvenne con la guerra voluta dall'Imperatore d'oriente Giustiniano, per la riconquista dell'Italia (535-553 d. C.). Successivamente, contendere il possesso della città a Bisanzio vennero i Longobardi (verso il 730 d. C.) e i Saraceni (842-871 d. C), i quali dopo ripetute incursioni, si stanziarono nel 847. L';occupazione araba durò circa 30 anni. Fu fondato un emirato e dotata la città di una moschea. I baresi estesero i loro traffici mercantili nei paesi dell'oriente ed assimilarono molta cultura araba: impararono i cambi di monete ad usare le loro unità di misura, fecero propri abbigliamenti prettamente arabi ed elementi dell'architettura musulmana. La dominazione cessò nel 1871, quando la città tornò sotto il governo bizantino come sede di un governatore generale "il catapano". Nel 1002 i saraceni tentarono di riconquistarla dal mare, ma furono allontanati dalla flotta veneziana. Nel 1009 Melo da Bari, raccogliendo il malcontento popolare nei confronti dei dominatori per motivi sia economici che religiosi, e con l'aiuto dei Normanni, organizzò una rivolta armata. Argiro, figlio di Melo, cessò le ostilità quando i Normanni che il padre aveva chiamati in aiuto come mercenari, cominciarono a stanziarsi in Puglia come padroni e dominatori.