In realtà esiste un'affermazione del Giustiniani che, riguardo a Cellamare dice:

"Si crede, che un tempo fosse stata murata..."

L. Giustiniani

Evidentemente le mura sorsero in epoca successiva al XII sec., per proteggere chi viveva all'interno del castello. (Si noti che fu questo il periodo in cui l'arcivescovo Giovanni V, con alcuni cittadini baresi, si stabilì nella villa Cella Amoris).
La cinta muraria circondava l'intero borgo, estendendosi lungo Largo Plebiscito, via Bari, Fuori le Mura, via Caracciolo, via Aia. Erano compresi nella cinta muraria il Castello e la Chiesa Madre, quasi a rappresentare due punti di forza uno rivolto ad ovest e l'altro ad est. Essi costituivano i centri attorno ai quali si svolgeva la vita sociale.
A differenza di altre città quali Barletta, Altamura... che avevano accesso al borgo secondo ogni punto cardinale, per un totale di quattro porte, Cellamare doveva averne una sola, probabilmente dove ora si trova la Porta Terra, che congiungeva Piazza Don Bosco e Corso Roma. La scomparsa delle mura risale al secolo scorso.