Un ricamo di pietra. La Chiesa è stata costruita dai Cavalieri Teutonici sotto gli auspici di Federico II di Svevia dove esisteva una cappellina dedicata a San Martino o forse a San Leonardo, patrono dei Teutonici, al quale è intitolata una delle più belle Poste del territorio andriese che la tradizione vuole che sia stata donata ai Teutonici dallo stesso Imperatore Federico II.

Pregevolissimo è il portale d’ingresso alla chiesa ritenuto, per la sua valenza artistica, "monumento nazionale". Formato da sette fasce finemente scolpite della larghezza complessiva di circa 120 centimetri, il portale è gotico a sesto leggermente acuto ed è tutto “un ricamo di pietra” con diversi motivi floreali. Nella lunetta centrale sono raffigurati il Salvatore con ai lati San Remigio e San Leonardo sormontati da due angeli, mentre, ai lati del portale ci sono i resti di due leoni stilofori come nelle altre chiese pugliesi del periodo svevo. Sul lato destro del portale è scolpito il Bafometto, uno dei simboli dei Templari.

Gli Agostiniani ebbero in uso la chiesa nel Trecento su invito del Duca Francesco I del Balzo e successivamente l’ampliarono consacrandola a Sant'Agostino. Come nella maggior parte delle Chiese, anche quella di Sant’Agostino subì nel Settecento un completo addobbo di stucchi barocchi.

Anche in questa Chiesa l’ebanista andriese Giuseppe Gigli realizzò un coro scolpito in noce e molto belli sono gli affreschi della volta che raffigurano momenti salienti della vita del Santo.

Adiacente alla Chiesa, l'antico convento oggi sede della Bibliooteca Comunale.

Stupendo il chiostro retrostante che completa l'intero complesso architettonico teutonico, oggi sede di un mercato coperto.

Il mistero della presenza teutonica è correlato al fascino letterario di questi monaci guerrieri ed alimentato dalle leggende che indicherebbero sotto il pavimento della Chiesa il luogo della sepoltura delle spoglie del Gran Maestro, quì traslate dalla città di Barletta dove erano custodite  dopo la morte avvenuta a Salerno nel 1239.