Non sono chiare le origini di Bari (Βαριον in greco, Barium in latino), ma da quanto emerso dagli scavi nell'area della chiesa di San Pietro, nella città vecchia, sembra ipotizzabile l'esistenza di un originario insediamento dell'età del bronzo, appartenente al popolo dei Peucezi. In epoca greca, la città assunse il nome di Barion.
Entrata a far parte del dominio romano, nel III secolo a.C. come municipium, Barium si sviluppò in seguito alla costruzione della via Traiana.
Dal IV secolo fu sede episcopale e dopo la caduta dell'impero romano fu contesa tra Longobardi e Bizantini (l'attuale struttura della "città vecchia" risale a quest'epoca, e si articola intorno alla corte del Catapano).
Successivamente fu in mano dei Berberi (dall'847 all'871 fu sede di un emirato) e quindi dei duchi longobardi di Benevento. Nell'875 tornò ai Bizantini che la crearono capitale del thema di Langobardia, comprendente l'Apulia e la Calabria.
Liberata, dopo sei mesi di assedio dei Saraceni, dalla flotta veneziana, nel 1002 si ribellò sotto la guida di Melo di Bari (nobile barese) al governo fiscale del catapano bizantino, riuscendo nel 1018 ad ottenere la propria autonomia.
Ultimo possedimento bizantino in Italia, nel 1068, la città di Bari fu assediata dai normanni, che la strapparono ai bizantini nel 1071, e nel 1087 vi furono portate le spoglie di san Nicola di Myra. Tra il XII e il XIV secolo fu porto di partenza per le Crociate.
Nel 1098 nella cripta della nuova basilica di san Nicola, si riunì il concilio presieduto da papa Urbano II, al quale intervennero oltre 180 vescovi riunitisi per discutere di problemi dogmatici inerenti ai rapporti tra la Chiesa ortodossa e Chiesa Romana all'indomani del Grande Scisma.
Distrutta da Guglielmo il Malo nel 1156, tornò a rifiorire in epoca sveva, intorno al castello fatto erigere da Federico II su preesistenti fortificazioni normanne.
Un lungo periodo di decadenza (dovuta soprattutto alla politica vessatoria dei governi dominatori) caratterizzò la città sotto le dominazioni di Alduino Filangieri di Candida, Maestro della Regia Corte e Giustiziere di Bari dal 1284, e quelle angioina, aragonese e spagnola, interrotto dallo splendore sotto gli Sforza, con le duchesse Isabella d'Aragona e Bona Sforza. Bari subì anche la dominazione veneziana, grazie alla quale si ebbe l'ampliamento del porto e un periodo molto florido, favorito anche dal commercio di prodotti dell'entroterra, molto richiesti sui mercati esteri.