Omkring 1080 bygges Skt. Nicolai Kirke - Aarhus’ første domkirke, som var opkaldt efter de søfarendes helgen. Den blev bygget rundt om Kryptkirken, der fungerede som kirkerum i Skt. Nicolai. Den mistede imidlertid denne status, da Aarhus’ nuværende domkirke Skt. Clem­ens Kirke blev bygget i 1200-tallet.

Omkring 1240 kom dominikaner­munkene til Aarhus. De overtog Skt. Nicolai Kirke og ombyggede den gamle frådstenskatedral til en gotisk munkestensbygning. Vor Frue Kirkes nordmur er den ældste væg i kirken, og den består delvist af fråd­sten fra den oprindelige domkirke, som kan ses fra klostergården.

I løbet af middelalderen udbyggede munkene kirken: Kirkens kor fra cirka 1250 blev udvidet, så de mange munke kunne samles her under gudstjenesten. Kirkeskibet er fra cirka 1350, sideskibet fra omkring 1450 og tårnet fra cirka 1500.

I forbindelse med reformationen måtte munkene forlade klosteret og kirken, og begge dele overgik til Kronen. Kirken fik kort herefter navnet Vor Frue Kirke og blev sognekirke. Kong Christian den 3. bestemte samtidig, at klosteret skulle anvendes som ”almindeligt hospital for syge og fattige”, en funktion, der varede helt indtil 1930’erne.

I dag fremtræder kirken som et resultat af en gennemgribende restaurering, der fandt sted i midten af 1950’erne. I øvrigt samme restaurering, som resulterede i fundet af Kryptkirken.