Helt hvor gammel Sct. Marie kirke er vides ikke, men man ved dog, at den har været til i 1541, da Kong Christian III kaldte Johan Wachter som præst ved kirken i St. Jørgensby. Den gamle Sct. Marie Kirke har kun været lille og har næppe kunnet give plads nok til byens tiltagende indbyggertal. Hertug Hans beslutter at udvide kirken. 

I 1594 begyndte man med at køre sten til kirken og grundstennedlæggelsen har fundet sted i 1595. 

I murankrerne på sydsiden ses årtallet 1599. Kirken stod færdig 1600 og blev indviet samme år. 

I sommeren 1881 besluttedes det at bygge et tårn over kirkens vestgavl. Det blev opført i 1883. Arkitekt Prale, Flensborg, udfø'rte tegningen og ledede arbejdet. Rendbjerg teglværk leverede stenene. Mur- og tømmerabejdet udførtes af bygmeter Julius Prühs i Grasten. Malermester FL Witt forgyldte kuglen, korset og spirene på de små hjørnetårne

Tårnet blev rejst den 8. oktober, korset og kuglen sat op den 10. oktober 1883. Kuglen indeholder en blykapsel med følgende tekst (i oversættelse):

"I dag onsdag den 10. oktober 1883, formiddag mellem 10 og 11, blev denne kugle og korset her i kirken indviet af førstepræsten P. Godt under nærværelse af kirkekollegiet og efter at kapslen var blevern lukket og lagt ind i kuglen, blev den af tømmermænd med Guds hjælp rejst på tårnet".

I 1924 gennemgår kirken en større istandsættelse der i hovedtræk omfatter:

1. Udbedring af pillerne og hvælvingribberne

2. Nye stolestader

3. Nye vinduer

4. Nyt orgel

5 Andre mindre forandringer, der kunne tjene til forskønnelse af kirken.

Renovering af kirkerum 1959-61

I gennemgik Sct.Marie kirke atter en større renovering af kirkerummet.

De gamle kirkebænke blev kasseret, gulvet blev renset for gamle gravsten og nylagt med ølandsfliser. En del epitafier fjernedes fra pillerne og der kom nyt orgel fra Marcussen og søn på 39 stemmer.

Hensigten med denne renovering har tydeligvis været at få et mere ”rent” og nøgternt rum.

Tårnet fra 1883 havde vist råd i træværket, og spiret blev ikke blot fornyet, men også stærkt forenklet bl.a. ved fjernelse af de små spir.