Vor Frue Kirke ligger udenfor voldene. Under Gorm den Gamle blev blev der i 948 indsat biskopper i Slesvig, Ribe og Aarhus. I Aarhus hed biskoppen, Reginbrand, og hans menighed benyttede en trækirke udenfor voldene. Denne blev så byens første domkirke. Frederik Danneskjold Samsøe, som var baron til Marselisborg og Christian 5‘s barnebarn, blev begravet her i 1770. Hans grav findes ikke længere.
I 1050 brændte Harald Hårderåde kirken, som derefter blev kirken afløst af en frådstenskirke, af hvilken man stadigvæk kan se krypten.
Omkring frådstenskirken blev i 1080-tallet bygget en teglstenskirke viet til Skt. Nikolaj. I 1200-tallet ophørte kirken med at være domkirke i forbindelse med at Skt. Clemens kirken blev bygget indenfor voldene, over Hellig Niels‘ grav af biskop Peder Vognsen. Kirken blev overtaget af dominikanerordenen, som de følgende år udvidede kirken og byggede klosterbygningerne.
Et af rummene i dominikanernes kloster kendes nu som klosterkirken, men var oprindeligt klostrets kapitelsal, altså munkenes samlingssal. Efter refomationen blev klostret indrettet som hospital, og rummet fungerede da som hospitalskirke.