L'origine del culto della Madonna di Sovereto per la città di Terlizzi s'intreccia fortemente con l'essenza più squisitamente agricola della città, una storia che profuma di terra e in cui s'incontrano e confondono elementi che sfumano dal mistico alla credenza popolare, fino ad eventi storicamente attestati.
Il racconto del ritrovamento dell'icona della Vergine con Bambino, dunque, segue due strade differenti, diramandosi in un terreno pregno di leggenda in cui non mancano forti richiami a parabole evangeliche, e nel terreno più razionale della storia in cui i fatti narrati non sono altro che echi di avvenimenti precedentemente verificati in territori situati più a oriente della città di Terlizzi.
Il racconto popolare narra di un pastore della città di Bitonto che, dopo aver portato a pascolare il suo gregge nel bosco di Sovereto, in territorio terlizzese, nel momento del ritorno smarrisce una pecora il cui belato, dopo tante ricerche, sente provenire da una macchia cespugliosa.
Ritrovata la pecora, vede filtrare da una cavità rocciosa vicina un misterioso raggio di luce; raggiunta la cavità carsica, il pastore rinviene sul fondo della grotta la preziosa icona della Vergine col Bambino
Avvertita la cittadinanza di Bitonto sul miracoloso ritrovamento, la notizia giunge altresì alle orecchie dei terlizzesi facendo conseguentemente nascere un contenzioso tra le due città su chi avrebbe preso in custodia l'icona poichè era stato sì un pastore bitontino a trovarla, ma in territorio di Terlizzi.
Per risolvere la questione terlizzesi e bitontini si affidarono a un giudizio divino: sarebbe stato Dio a scegliere la città verso cui si sarebbero diretti i due buoi, appartenenti alle due contendenti, attaccati al carro agricolo che trasportava il simulacro della Madonna.
Posti sulla confluenza delle due strade che portavano alle rispettive città, il bue di Terlizzi sferrò una poderosa incornata al bue di Bitonto costringendolo così a proseguire verso Terlizzi dove di lì a poco il carro ornato di fiori con la sacra icona entrò accolto dalla popolazione festante.
Il racconto leggendario, arricchito col tempo di particolari folkloristici, viene ridimensionato da fonti storiche che ricondurrebbero il ritrovamento dell'icona alla forte presenza nella zona di Sovereto di pellegrini e monaci eremiti provenienti dall'oriente, in particolare in seguito alle persecuzioni iconoclaste, che privilegiavano insediamenti rupestri, eremi e grotte come propri ricoveri.