Le ipotesi riguardanti le origini della città sono due.

La prima vuole che Barletta sia stata fondata nel IV secolo a.C. dai Bardei popoli illirico proveniente dalla Dalmazia, regione costiera adriatica ricca di isole che si trova nell'attuale ex Jugoslavia. I Bardei dopo varie lotte contro l'impero macedone, furono cpstretti ad abbandonare la loro patria sconfitti da Alessandro il Grande nel 336 a.C. e giunsero così sulle coste dell'Apulia lì al confine tra Daunia e Peucezia, dopo alcuni anni in cui si erano dedicati alla pirateria.

La seconda ipetesi sostiene che la città venne fondata dagli abitanti di Canosa tra la fine del V e gli inizi del IV sec. a.C.: questa tesi venne abbollata dal ritrovamento di tombe del VI - III sec. a.C. lì dove presumibilmente fosse il posto di Canosa.