La chiesa è nota anche come "chiesa di San Lorenza extra moenia" o "chiesa di San Lorenzo fuori le mura", per via della sua posizione esterna al muro di cinta della città. Tale caratteristica è rinvenibile in altre chiese intitolate a San Lorenzo, come ad esempio la Basilica di San Lorenzo fuori le mura, a Roma.

 

La chiesa risale con molta probabilità al XIV secolo, dal momento che le prime testimonianze scritte della presenza della Chiesa risalgono al 1330. Essa ha subito, nel corso del tempo, dei rifacimenti anche sostanziali (specie nel XVIII secolo) che ne hanno alterato la struttura originaria. Certo è il suo restauro nel 1717, promosso da un certo Giuseppe Carlucci: la chiesa versava in uno stato di abbandono e degrado nel corso dei secoli XVI e XVII e l'opera di restauro ha apportato cospicue modifiche. La forma in cui si presenta oggi risente dello stile tardobarocco (specie la facciata).

 

L'iscrizione in caratteri gotici sul portale di ingresso e il giglio angioino sullo stesso sono sicuramente gli elementi più antichi della costruzione e inducono a ritenere che la chiesa originale risalga alla prima metà del XIV secolo.

 

L'iscrizione è stata oggetto di studio da parte degli studiosi di varie epoche storiche, dal momento che in essa si fa esplicito riferimento alla leggenda dei mirmidoni (la cui regina era Altea, da cui Altilia) e sembrava pertanto la più antica prova della validità storica della leggenda. Domenico Santoro (1688) addusse per primo l'iscrizione sul portale a sostegno della validità del toponimo Altilia, e affermò nella sua opera Descrizione della città di Altamura (1688) che la chiesa e l'iscrizione risalivano a prima dell'anno Mille. Pertanto arrivò alla conclusione che anche la leggenda doveva essere antica. Ottavio Serena confutò le osservazioni di Domenico Santoro e postdatò di molti secoli la costruzione della chiesa e l'iscrizione.