Il santuario di Maria SS. delle Grazie venne eretto sul finire del XVII sec. sulla collina di Montefreddo (in fondo a Corso Vittorio Emanuele), luogo ove , verso la metà del VI sec., avvenne il miracolo di S. Antonio Abate per cui Genzano non fu più rasa al suolo. La scelta di dato luogo per la costruzione del santuario mariano cionostatante sembra sia dovuto ad un secondo evento miracolistico:"narra la leggenda che pochi anni dopo l'invenzione dell'Effigie, il 2 Luglio, mentre si trasportava in solenne processione la Madonna delle Grazie il corteo, giunto sulla collina di Montefreddo, non potette proseguire perchè l'Effigie improvvisamente, si era impensantita al punto da non poter essere mossa in alcuna maniera...(E. Lorito, Genzano di Basilicata - p.115).

Questa Effigie, affresco rappresentante la Vergine col Fanciullo, è da allora conservata in una nicchia ricavata nell'abside centrale del santuario, essendo stata precedentemente, e in modo provvisorio, collocata in una piccola cappella fatta erigere in contrada Capo d'Acqua, cappella che fu abbandonata e perciò scomparve dopo la collocazione dell'Immagine nella sede definitiva.
Da allora la Madonna delle Grazie è protettrice dell'Università di Genzano anche se la devozione del popolo Genzanese per la Vergine delle Grazie si può far risalire a tempi precedenti, infatti, nella visita pastorale di mons. Giovanni Michele Saraceno, avutasi nel 1544, si fa già riferimento alla presenza di una cappella sita fuori le mura "sub vocabolo Sancte Marie de Gratie".
Nella platea del 1701 si fa riferimento "agli infiniti miracoli, e gratie, che di continuo ha fatto , e fa, tanto prima che fusse ritrovata, quanto dopoi, che non basterebbe lingua humana a raccontarli,  ma le genti che vi concorrono, ne ponno fare attestati" (Archivio Diocesano Acerenza). Tra i miracoli che si verificarono nel santuario, famoso era quello della lampada, secondo la tradizione ritrovata insieme all'immagine della Vergine e rimasta prodigiosamente accesa fin da quel giorno, nonostante nessuno avesse provveduto ad aggiungervi altro olio, il quale anzi veniva distribuito ai pellegrini in piccoli vasi, senza tuttavia esaurirsi. Il prodigio è attestato, tra l'altro, nel verbale della visita pastorale effettuata nella Chiesa il 19 maggio 1704.
L'11 maggio 1845, domenica di Pentecoste, ricorrendo la festa in onore della Madonna, durante la messa solenne cadde un cero acceso e diede fuoco ad un drappo; in pochi minuti l'intero addobbo della Chiesa andò in fiamme.I fedeli, presi dal panico, si precipitarono verso l'uscita e nella calca una trentina di persone persero la vita. Un'epigrafe su pietra rettangolare posta nel pronao della Chiesa, ricorda una delle vittime della tragedia tramandata attraverso un componimento dialettale attribuito a certo Donato Rizzi. Riaperta al culto nel 1850, fu distrutta dal violento terremoto del 16 dicembre 1857 e ricostruita nel 1878.
Nel 1944-45 tutto l'interno venne sistemato con un soffitto a cassettoni e i riquadri affrescati dal pittore Domenico Pennino. Al termine dei lavori, la Chiesa fu solennemente consacrata il 10 Novembre 1945.
Il 25 settembre 1954 la venerata Immagine fu incoronata da S.E. mons. Enrico Nicodemo, Arcivescovo di Bari.
La notte tra il 30 e il 31 dicembre 1974 ignoti ladri trafugarono le corone, il 9 agosto 1976 l'Arcivescovo mons. Giuseppe Vairo rifece il rito dell'incoronazione , rimettendo sul capo della nostra Protettrice nuove corone d'oro, rifatte per interessamento del comitato festa e il contributo di tutto il popolo.
La Chiesa rimasta fortemente danneggiata dal sisma del 23 novembre 1980, fu riaperta al culto il 20 novembre 1988 da S.E. mons. Michele Scandiffio, Arcivescovo di Acerenza.