Nei primi anni del Mille i Benedettini, provenienti dall’Abbazia di Santa Maria di Anzi, costruiscono, nei pressi di Molfetta una chiesa con il Monastero di Santa Maria e San Giovanni. Nel 1095 Ruggero, figlio di Roberto il Guiscardo, amplia il Monastero e costruisce due ospedali per i crociati, per curare cioè i pellegrini ammalati ed i feriti reduci dalla Terra Santa. Siccome molti dei crociati, affranti dalle sofferenze, terminano in questo ospedale la loro esistenza, nel 1162 Guglielmo I, re di Napoli, costruisce un cimitero per la loro sepoltura ed, in seguito, edifica un magnifico tempio in onore della Madonna sotto il titolo di Regina dei Martiri, in ricordo dei valorosi testimoni della fede che avevano combattuto per amore di Cristo. L'icona della Vergine, fu portata dai crociati nel 1188 e venne collocata sull’altare maggiore della Chiesa di Santa Maria. È un dipinto ad olio, su tavola di cedro, di cm 100 X 66, raffigurante la “Madonna della tenerezza”. La Madonna tiene in braccio sulla sinistra Gesù Bambino che bacia ed abbraccia la mamma; con la mano destra Maria indica Gesù, a significare che Lei è la sicura via che porta al Signore. Negli angoli, in alto due Angeli reggono un drappo ornamentale. La devozione ed il culto alla “Madonna dei Martiri” vanno crescendo, i favori e le grazie ricevute si moltiplicano ed il Santuario è progressivamente abbellito di marmi pregiati e d’opere d’arte. La Madonna è una sicura protezione contro le forze avverse della natura e le incursioni dal mare. I Turchi invadono Molfetta ed incendiano il Santuario, ma l’icona della Madonna resta illesa. Nel conclave del 24 agosto 1484, il Vescovo di Molfetta, Giambattista Cibo, è eletto Papa col nome di Innocenzo VIII; egli subito, con bolla pontificia del 1° giugno 1485, concede indulgenze a favore del culto della Madonna dei Martiri, nella domenica in albis e nella festa dell’8 settembre. Nel 1840 Valente Mauro Oronzo, per grazia ricevuta, dona al Santuario una statua in legno, realizzata dallo scultore napoletano Giuseppe Verzella, raffigurante la Vergine con il Bambino e due Angeli che pongono sulle spalle della Madonna un artistico manto di stoffa, secondo il modello dell’antica icona. E' questa l'immagine che viene portata ogni anno in processione nella festa dell' settembre.