Di origini incerte, le prime testimonianze certe risalgono alla Tavola peutingeriana dove "Bardulos" viene citata, ma alcune sepolture apule con reperti del IV-III sec. a.C. testimoniano un insediamento preesistente all’epoca romana. Durante le invasioni longobarde fu rifugio per gli abitanti di Canosa. Crebbe di importanza nel periodo medioevale come fortezza e centro commerciale dei Normanni ed inseguito divenne una tappa per i Crociati diretti in Terra Santa. Il suo massimo splendore lo raggiunse sotto il dominio degli Angioini quando, grazie alla sua flotta, si arricchì la città con i commerci con l’Oriente. Famosa è la disfida di Barletta che, nel 1503, oppose 13 cavalieri italiani guidati da Ettore Fieramosca a 13 francesi.