Usciti quindi da porta La Maja, rivolgendo lo sguardo a sinistra, si trova un segno evidente della cinta muraria che sin dall'antichità cingeva il nucleo abitativo. La datazione più antica delle mura risale al periodo normanno (XI-XII sec.), anche se non è da escludersi un'origine anteriore a tale data. Ampliamenti risalgono all'età svevo-angioina (XIII-XIV sec.). Con la dominazione aragonese e a seguito della crescita demografica, la città si dota di una seconda cinta muraria. Si ha notizia dall'avvocato Martucci-Zecca di un rifacimento delle mura tra Porta Baresana e Porta La Maja (lato est) a fine ‘500, reso necessario dal cattivo stato di conservazione. Questo tratto oggi risulta in parte occultato dalla costruzione di locali addossati alle mura agli inizi del ‘900, per farne sede del servizio elettrico. Sono visibili nella parte superiore due giardini pensili: uno è di pertinenza della Chiesa di San Francesco la Scarpa ed è destinato ad accogliere un teatro all’aperto. Le mura in questo lato del centro antico erano rese più sicure dalla presenza della Lama Balice, un solco di origine carsica, che costituiva una difesa naturale. Di contro, a nord (la parte della città verso il mare) l’abitato era ulteriormente protetto da un fossato artificiale, ricoperto a fine ‘800.
Attualmente riemergono, a volte inglobate e nascoste da abitazioni o strade, le vestigia delle antiche mura, che dalla carta Azzario della fine del ‘500 risultano costituite da 28 torri e 5 porte, per una lunghezza di 2.015 metri. Anche durante il restauro del teatro Traetta sono emersi, e sono oggi visibili, i ruderi di una porta e alcune sezioni di mura. Solo due delle cinque porte che costituivano l’accesso al centro antico sono sopravvissute: Porta Baresana e Porta La Maja. Le rimanenti tre porte sono andate distrutte nel corso del tempo. Procedendo a sinistra di Porta La Maja, si ergeva la Pendìle, affacciata sul Tiflis, il torrente che attraversa la città nell’alveo di Lama Balìce, che fu demolita nel 1890. In corrispondenza di questa si trova la chiesa di Santa Maria alla Porta (1450). Poco più avanti in via Solferino, di fronte al vecchio macello risalente al 1890 e oggi dismesso, si riconosce un altro tratto di mura con una torretta detta ‘Muro Carvutto’. Da qui parte un'altra sezione delle mura di matrice angioina, interrotte da una bellissima torre con zoccolo e feritoia, che arriva a piazza Robustina, così chiamata perché posta in direzione di Ruvo (lat. Rubos). Questa porta venne distrutta nel 1898: una lapide posta sul vicino Palazzo Stellacci ne ricorda la presenza.
Proseguendo su via Muro Porta Robustina si trova un'altra torre quadrata, detta ‘Caldarola’, e si arriva così al punto dove si ergeva porta Nova, rivolta verso Terlizzi e distrutta nel 1883. Nelle vicinanze si segnala la chiesa dell'Annunziata. Quasi nulla è rimasto fino a Porta Baresana, ad eccezione del basamento di una piccola torre cilindrica in corrispondenza del n. 20 di via Matteotti.
