La città è stata difesa da un cortina muraria che correva lungo il perimetro dell’attuale centro storico. Le fortificazioni più antiche, quelle greche, che risalgono al IV-III a.c. sono state rintracciate a Porta Schiavoni. Le mura sono costituite da pesanti blocchi di calcarenite, materiale estratto nella Murgia di Montescaglioso, sovrapposti elegantemente, con uno spessore di circa tre metri. Nuove interpretazioni portano a ritenere che non si tratti di un tratto della fortificazione della città, bensì di una poderosa opera di terrazzamento, realizzata per contenere quella porzione di abitato adiacente al pendio.
In età tardo imperiale la decadenza della città ed il calo demografico spingono la popolazione ad arroccarsi intorno ad una roccaforte eretto sul punto più alto della collina, l’attuale Rione Torre Vetere. Il centro medievale, probabilmente longobardo, è attestato per la prima volta in un documento di 893 e resiste ad un assedio Saraceno nell’anno 1003. In una veduta della città del 1593 la roccaforte longobarda è visibile ed è costituita da una torre quadrangolare, circondata da una cinta rafforzata da torri più piccole.
Con l’infeudamento di Montescaglioso ai Normanni la città acquista un grosso prestigio, infatti il feudo passa da Roberto, nipote del Guiscardo, alla famiglia Macabeo, un cui membro Rodolfo, sposa Emma, figlia di Ruggero I di Sicilia. Ai due coniugi si deve l’ampliamento della città con la ricostruzione della cinta fortificata e l’edificazione di un nuovo castello nei pressi di Porta Maggiore. I lavoro hanno avuto inizio nell’ultimo decennio dell’XI sec. e si sono conclusi intorno al 1119. Tratti della fortificazione normanna sono ancora oggi visibili intorno all’Abbazia e nel rione Torre Vetere. La fortificazione normanna sarà preservata fino alla metà del secolo XIX, quando inizierà l’opera di demolizione.