L'origine della costruzione del Castello è da riferire all'età sveva, secondo la testimonianza di Riccardo di San Germano, che la colloca intorno al 1227, e cioè proprio negli anni in cui è attestata la presenza di Federico II di Svevia a Brindisi, tra il suo matrimonio con Jolanda di Brienne (1225) e la partenza della crociata (1228). Gli storici locali riferirono, senza alcun riscontro archeologico, che per la sua costruzione furono utilizzati materiali di reimpiego romani (in particolare dall'anfiteatro).

Dai registri angioini veniamo informati che Carlo I d'Angiò provvide al restauro del Castello (sopraelevazione delle torri) e all'edificazione di un palazzo reale al suo interno (1272-1283), dando l'incarico di supervisore all'architetto Pierre d'Angicourt.

Si deve a Ferdinando I di Napoli il primo ampliamento del maniero brindisino (metà del XV secolo): la modifica, dettata dalle nuove esigenze belliche dovute all'adozione delle armi da fuoco, consistette nella costruzione di un'ulteriore cinta muraria, più bassa e più spessa della precedente, munita di torrioni bassi e circolari dotati di scarpa. Il precedente fossato venne coperto da volte e furono creati così nuovi ambienti, adatti ad ospitare uomini in arme, ma anche la popolazione in caso d'emergenza.

Nel 1496 il Castello insieme alla città venne consegnato sotto il "protettorato" della Repubblica di Venezia, venendo descritto come "bello e fortissimo, che domina la città e gli altri castelli". Altre modifiche vennero operate nel 1526 (da Giovani Battista Pignatelli) e nel 1530 (da Ferdinando da Alarcon) al fine di assicurare una difesa più efficace, con la sopraelevazione dei parapetti e la realizzazione della Batteria di Levante e del Baluardo della Campanella sul lato mare. In seguito l'impianto del Castello venne ulteriormente fortificato con l'edificazione di due grandi "puntoni" poligonali verso il porto.

Dopo essere stato adibito a penitenziario, all’inizio del XIX secolo, diviene con l’Unità d’Italia sede di Comando della Marina a Brindisi, subendo alcuni interventi di adattamento ma conservando intatta la struttura.

Il Castello si sviluppa attorno ad un cortile di forma quadrangolare trapezoidale circondato da un'alta muraglia munita di un magnifico mastio con funzione di entrata e altre sei torri, due di forma circolare tre a pianta quadrata e una pentagonale: questo nucleo originario appartiene al periodo svevo. La cortina più esterna è chiaramente riferibile al XV-XVI secolo: sono qui presenti infatti i classici torrioni circolari tardo medievali e rinascimentali, muniti di artiglieria. Inoltre sull'arco del corridoio che dalla sala porta alla piazza d'arme è collocata la catena angioina che serviva a chiudere l'ingresso al porto interno nel XIV secolo.