Kirken er opført sidst i 1100-tallet efter biskop Absalons død og blev indviet den 14. september 1209.
Byggeriet af kirken blev finasieret med indtægterne fra den eksisterende Skt. Clemens Kirke. Det var dog ikke tilstrækkeligt, så også indtægterne fra en række ejendomme i omegnen måtte bruges til at betale for kirkebyggeriet.
Kirken blev placeret på byens højeste punkt hvor to af byens indfaldsveje, Nørregade og Vestergade, mødtes.
Den oprindelige kirke var bygget af kridtsten. Den brændte i 1314 og blev genopbygget i teglsten. Denne kirke har haft en vis lighed med Sankt Peders Kirke i Malmö, som var bygget omkring samme tid. Stilen var tidlig gotik, og inspirationen hentet fra franske kirker.
I 1485 blev der tilføjet et tårn og 30 år senere et spir.

Vor Frue Kirke som den så ud i 1700-tallet.
Vor Frue Kirke var fra starten Københavns vigtigste kirke og havde seks kanniker (dvs. præster) og en dekan. Efter genopbygningen i 1300-tallet blev antallet af kannikker udvidet til det dobbelte. Dertil kom et antal hjælpepræster.
Kirken ejede omfattende ejendomme – op i mod 100 fæstegårde – over store dele af det østlige Sjælland.
Kirken fik med tiden flere og flere sidealtre, og i 1500-tallet var der omkring 40. De forsvandt alle efter reformationen, men var forinden blevet hærget under kirkekampen i 1530, hvor ophidsede borgere trængte ind i kirken og ødelagde en del af de mange helgenbilleder.
Vor Frue Kirke var dels sognekirke for den vestlige del af byen, dels Københavns Universitets kirke. Men den var desuden tilknyttet domkirken i Roskilde som en kollegiatskirke, dvs. at den havde visse, selvstændige rettigheder. Endelig var den en slags uofficiel hovedkirke for hele landet.
Siden kong Christian den 1., var der her kongerne blev kronet, og dåb, vielse m.m. i kongehuset foregik her. Mange adelige og gejstlige blev desuden begravet i kirken.
Under reformationen i 1536 blev kirken stormet og biskoppen sat i fængsel i Blåtårn på Københavns Slot. Kapitelshuset overgik til universitetet.
I tilknytning til kirken lå Vor Frue Skole.
Kirken brændte ved Københavns store brand i 1728. Man forsøgte at redde den ved at sprænge en naboejendom i luften så ilden blev standset – men blot med de resultat at gnister fra eksplosionen antændte kirken.
Under bombardementet af byen i 1807, sigtede englænderne efter kirkens spir. Kirken blev ramt og brændte ned.
Efter krigen fik arkitekten C. F. Hansen til opgave at tegne en ny kirke, som fik en klassicistisk stil. Hansen havde tænkt kirken uden et tårn, men det blev kongen ked af, og beordrede ham til at tilføje et tårn.
Nogle mente, at kirken også burde have et spir. Byens mæcen, brygger Carl Jacobsen tilbød at bekoste opførelsen af et spir, men han døde inden tanken blev realiseret.
Syd for kirken lå i 1700-tallet en kirkegård ud mod gaden Dyrkøb. Kirkegården nedlagt igen i 1760, da man anlagde Assistens Kirkegård udenfor byens volde.