L’opera prese inizialmente il nome di Baluardo del Cassero dato che si trovava sulla parte più alta della cinta muraria.
In seguito venne rinominato Bastione San Paolo per la sua vicinanza alla chiesa che i Cappuccini dedicarono a San Paolo quando si insediarono sul colle intorno al 1555. Il progetto fu stilato da Antonio da Sangallo il Giovane, uno dei più insigni architetti militari dell’epoca, con la collaborazione del topogrado Bartolomeo De Rocchi. L’inizio dei lavori si colloca intorno alla fine degli anni ’30 del XVI secolo e si sa dalle carte dell’epoca che con certezza nel 1569 il baluardo era terminato. Il bastione si presenta con 123 metri di lunghezza su 4 lati, un’altezza che arriva oltre i 16 metri e uno spessore di oltre 3 metri in alcuni punti. Esso si sviluppa su tre livelli:
1 - di poco superiore all’altezza del fossato che anticamente lo circondava, presenta due locali casamattati (protetti) con due postazioni per i cannoni simmetriche rispetto all’ unica porta d’accesso esterna protetta a sua volta da postazioni fisse per fucilieri; due aperture sulla volta consentivano lo smaltimento dei fumi prodotti dai tiri d’artiglieria;
2 - il livello intermedio presenta tre grandi ambienti voltati che davano su un terrapieno scoperto, corrispondente alla parte alta dei locali sottostanti, sul quale venivano posizionate altre artiglierie;
3 - il livello più alto corrispondeva alla quota della strada di accesso dall’interno della città e presentava altre postazioni di artiglieria; questa volta rivolte sia verso la piana degli Orti che verso la rupe sul mare.