Kirken blev oprindeligt opført af bindingsværk i 1665-1667. Senere blev der foretaget flere ombygninger og kirken står i dag (nu) som en nyklassicistisk præget langbygning. Oprindelig var kirken for den tysktalende del af byens befolkning og fungerede allerede fra starten som garnisonskirke med særlige rettigheder og pligter.

I kirkens indre er der ved den nordlige langside et pulpitur (galleri) i to etager. Døbefonten er en ¾ kopi af Bertel Thorvaldsens døbefont i Vor Frue Kirke i København. Et af kirkens klenodier er et krucifiks udført af billedhuggeren Astrid Noack. I 1995 fik kirken yderligere et klenodie i form af et nyt alterparti udført af maleren Svend Havsteen-Mikkelsen og sønnen Alan.

Svend Havsteen-Mikkelsen har udført selve alterbilledet over temaet korsfæstelsen og Alan har stået for de to flankerende vinduer, der er udført som røgfarvede glasmosaikker symboliserende det menneskelige sind (mørke og lyse tanker).

Sct. Michaelis kirke er omfattet af en særordning, der bl.a. pålægger kirken at betjene garnisonen og udpege en garnisonspræst. Øvrige kirker, der er underlagt disse særregler, har ikke længere en garnison tilknyttet, hvorfor Sct. Michaelis kirke reelt kan betegnes som Danmarks eneste garnisonskirke.