I den nuværende Vor Frue Kirke indgår rester af en ældre stenkirke opført af frådsten og kampesten. Ruinen af en treskibet krypt overdækket af 12 grathvælv, der var båret af otte retkantede piller, blev udgravet i 1955 under kirkens kor og indgår i restaureret stand i den nuværende kirke. En tydelig fuge markerer grænsen mellem originalt og genopført murværk. Også væsentlige dele af kirkens nordmur, som er synlig fra klostergården, stammer fra den første kirke og rummer bl.a. en stor rundbuet portal. De arkitektoniske træk placerer opførelsen omkring år 1100. Meget tyder på, at denne kirke har været stiftets første domkirke, som antagelig var viet til Sankt Nikolai og må have rødder tilbage til 948, hvor stiftet nævnes første gang.
Det er uvist, hvorfor domkirkefunktionen blev overflyttet til den nuværende Sankt Clemens Kirke på Store Torv, men herved kunne den ældre stenkirke overgå til en anden funktion. Ca. 1225‑50 blev bygningen skænket til en gruppe tiggermunke af dominikanerordenen, som grundlagde et kloster på stedet. Bevarede seglaftryk fra klosteret afbilder Jomfru Maria, som klosteret må have været indviet til, og er baggrund for, at dette navn knyttedes til kirken efter Reformationen.
En tilmuret dør i kirkens nordside omgivet af riflede og glaserede tegl viser, at munkene ved ankomsten slog sig ned på kirkens nordside, hvor de må have opført lettere bygninger af træ. I anden halvdel af 1200-tallet indledtes en stor byggefase. Et nyt langhuskor af tegl i unggotisk formsprog opførtes med bibeholdelse af den ældre krypt. I fundamentet til østgavlen placeredes en flot runesten fra ca. år 1000, den såkaldte Århussten 5. Hele fire runesten er gennem tiden fundet blandt klosterets fundamentsten. Det velproportionerede kor oplyses af høje, slanke, dobbeltsmigede vinduesåbninger og tilhører unggotikkens bedste eksempler. Riflede og glaserede tegl har i vidt omfang dekoreret false og åbninger i murværket, mens enkelte baser og kapitæler er udført i hvid kalksten. Da det er usandsynligt, at skibet har fået hvælv først, antages det, at koret fra begyndelsen har haft hvælv. Disse var båret af dværgsøjler med kapitæler udformet som fine, kronede hoveder udført i kalksten. Hvælvene må have svaret til det bevarede ottedelte hvælv i sakristiet, men de blev af uvisse årsager udskiftet med de nuværende stjernehvælv i 1490, der er dateret af en bevaret indskrift i koret.
I midten af 1300-tallet blev det ældre skib ombygget og overhvælvet i højgotisk stil, og i vestgavlens sydlige hjørne tilføjedes et kantet trappetårn. En indskrift på skibets vestligste hvælvkappe fortæller, at de er givet af ridder Stig Andersen Hvide og hans kone, Tove.
I kirkens kor ses spor efter flere rækker af våbenskjolde, der opregnede klosterets velgørere, som formentlig indgik i munkenes bønner. Der er rester af flere udgaver fra både høj- og senmiddelalder, og skjoldfriserne må være opdateret ad flere omgange.
I senmiddelalderen føjedes kapeller til kirkens sydside, som tilsammen kom til at danne et egentligt sideskib.
Til afløsning for de første, lettere bygninger opførte munkene fra anden halvdel af 1200-tallet grundmurede bygninger i tegl. Af disse er der rester bevaret i nordfløjen. Fra klostergården kan ses en bevaret fin portal, hvis kragsten udgøres af dårligt bevarede men oprindelig fint huggede kalkstenshoveder samt højere oppe på murfladen en række små, lancetformede vinduer. Lyset strømmede ind ad vinduerne til brødrenes spisesal, refektoriet, som opførtes samtidig med den oprindelige østfløj. Også i vest opførtes tidligt en smal fløj, og allerede omkring år 1300 må klosteret have udgjort et firfløjet anlæg.
I senmiddelalderen indledtes en storstilet bygningskampagne, som udvidede og omdannede klosterfløjene markant. Østfløjen nyopførtes fra grunden, øst for sakristiet opførtes det nuværende spinkle klokketårn, og nord- og vestfløjen blev udvidet og forhøjet. Fra nordfløjen udgik desuden to udløberfløje, og rundt i klostergården rejstes en hvælvet korsgang i to stokværk til at forbinde det hele. Af korsgangen er bevaret fire fag med rigt profilerede åbninger, som afslører, at byggeriet har været af høj kvalitet.
Rester fra klostertiden er bevaret i nordfløjens såkaldte munkestue, der oprindelig var køkken. I vestfløjen er bevaret en hvælvet sal med kalkmalerier, som antagelig var modtagerum for gæster.
Klosterfløjenes udseende er i dag stærkt præget af to store restaureringer. Den første blev udført i årene 1878‑79 og stort set uden bevaringshensyn. I 1950’erne forsøgte man i et vist omfang at råde bod på dette ved delvis at genskabe ældre træk. Den hårde skæbne til trods udgør klostergården fortsat et af Aarhus’ fineste og mest autentiske middelaldermiljøer.
