Den ældste historie 

Vor Frue Kirke er opført på byens højeste punkt ca. år 1200, men meget tyder på, at kirkebakken har været et helligt sted, længe før kristendommen kom til Danmark.

Den ældste del af kirken er en senromansk langkirke i røde munkesten. Den har formodentlig været to-skibet med søjler i den nuværende midtergang. Tilmurede vinduesåbninger kan stadig ses i murværket.

I en senere gotisk byggefase kom sakristi, våbenhus og sideskibe til, koret blev ombygget og der blev opført hvælvinger.

Tårnet er en senmiddelalderlig tilføjelse. Da kirkens gavl ikke var lige, står tårnet skævt på kirkerummets midterakse.

Efter reformationen

Kirkens hovedalter var i den katolske tid indviet til Vor Frue (jomfru Maria). Herudover var der syv altre, som alle blev fjernet efter reformationen i 1536.

Fra 1600-årene har kirken bevaret ikke alene alter og prædikestol, men også ligsten, klokke, sølvtøj, en Chr. IV bibel, en Lutherpostil og et dåbsfad.

I midten af 1700-årene fik prædikestolen, der tidligere havde været placeret nede i skibet, sin nuværende plads. Døbefonten blev ligeledes flyttet op i koret.

I 1768 fik kirkens tårn pyramidetag med et dobbelt lanternespir.

Restaurering 1884

I 1884 gennemgik Vor Frue Kirke den helt store restaurering. Kirkens hvide mure blev afrenset, og de røde munkesten kom frem i dagens lys. Tårnet blev skalmuret, og kirken fik isat nye vinduer. Hovedindgangen blev flyttet fra det gamle våbenhus i syd til tårnet, og kirkens middelalderlige sakristi blev revet ned og erstattet af et nyt.

Også indvendigt skete der store forandringer. Det nye våbenhus i tårnet blev forsynet med hvælving, væggene i kirken blev pudset lige og glatte, koret blev hævet to trin og der blev lagt nyt flisegulv. Døbefonten, kirkebænkene og lysekronerne er også fra denne periode.

1900-tallet

Op igennem 1900-tallet gennemgik Vor Frue Kirke kun mindre ændringer. Udsmykninger med kalkmalerier på vægge og hvælvinger var meget udbredt i første del af århundredet. Den seneste bemaling blev foretaget i 1930..

I 1960 blev kirkens indre istandsat, og træværkets brune farvesætning blev ændret til lysegrå med blå/grønne felter.

Renovering 2004

Da man i begyndelsen af 1990erne fjernede gulvtæpperne i kirken, kom knækkede gulvfliser til syne, og behovet for et nyt gulv blev aktuelt. En kalkning var desuden nært forestående, og man valgte derfor at benytte lejligheden til at få skabt helhed i kirkerummet med en helt ny farvesætning. Renoveringen blev påbegyndt i januar 2003 og afsluttet knap to år senere.

Hvælvingerne blev afrenset, og kirkens vægge og hvælvinger blev kalket hvide. Gulvet fra 1884 ønskede Nationalmuseet bevaret. Der blev dog givet tilladelse til, at et nyt gulv kunne lægges oven på det gamle. Det gamle gulv er bevaret i våbenhuset og i dåbsværelset.

Malerierne på alter og prædikestol blev renset, og træværket blev malet med sort, bladguld og okkerfarver. Prædikestolens figurer blev bemalet for at fremhæve de mange detaljer.

De øverste kirkebænke i hovedskibet og i sideskibene blev fjernet og erstattet af stole. Der blev gjort plads til et kororgel i søndre sideskib og flygel i det nordre sideskib. Kirkebænkene blev malet i en dyb violet farve, afstemt efter de nye glasmalerier af Trondur Patursson.

Hver tid har sat sit præg på Vor Frue Kirke, hvilket er et udtryk for, at kirken ikke kun er et historisk rum, men også en nutidig ramme om mødet mellem det evige og det foranderlige.