Graus va ser un enclavament important ja des d'època romana, doncs es troba en la confluència dels rius Éssera i Isàbena i per tant des d'aquest indret es controlava l'accés a les valls del nord. Va ser una important plaça musulmana, doncs era un punt estratègic per a repel·lir els atacs cristians del nord. Per aquest motiu Ramir I d'Aragó va intentar conquerir-la, però en 1063 va ser ferit de mort durant el combat. Va ser el seu fill, Sanç Ramírez el que en 1072 va aconseguir conquerir-la i annexar-la al regne d'Aragó. Un cop conquerida, va posar la vila sota la protecció del monestir de San Victorián.

La vila estava defensada per un castell, situat en la part més alta de la penya del Muralt, del que avui amb prou feines es conserven les restes d'una torre circular d'uns set metres de diàmetre i quatre d'alçada. També es poden veure algunes petites filades de carreus, que potser correspondrien a fragments de muralles.

Cap a l'any 1200 es va construir, en la mateixa penya del Muralt, una petita capella dedicada a Santa Maria. Aquest temple va ser substituït per l'obra actual l'any 1640. Les obres d'aquest temple renaixentista les va dirigir el mestre Joan Zeant i a la seva mort en Joan de Marta, per ordre del bisbe d'Osca, Esteve d'Esmir, que va morir en 1654, quatre anys després de la finalització del temple. Com a impulsor del santuari, el bisbe  es va fer enterrar en aquest indret.

L'església respon al model típic del renaixement aragonès, on es continuen utilitzant les formes constructives característiques del gòtic, com les voltes estrellades o les rosasses. Té una sola nau capçada per un absis poligonal.

En el mur nord podem veure les restes de l'antiga construcció romànica.  En ell podem veure una petita porta de mig punt, lleugerament elevada respecte al nivell de terra i una capella, amb volta de canó, dedicada a sant Josep.

Val la pena pujar fins al santuari per gaudir de les dues espectaculars galeries, la superior amb columnes estriades i amb espiral, que conformen un espai sensacional.

En sortir del poble per dirigir-nos al temple, trobem dos arcosolis al marge dret del camí, on s'allotgen dos sepulcres amb motius heràldics esculpits. El plafó informatiu ens diu que pertanyen a Roderic de Mur i la seva esposa, que vivien en el Palau dels Mur del mateix poble. En algun moment posterior a 1969, els dos arcosolis i sepulcres van ser traslladats de la seva ubicació d'aleshores, que era el cementiri. Tampoc es coneix per què van anar a parar a aquell lloc. Encara resulta més sorprenent veure com en aquest darrer trasllat els arcs van passar de ser apuntats a ser de mig punt...