I 1600-tallet var København en befæstet by og soldaterne, som skulle forsvare byen, lå i en garnison indenfor voldene.
Der var brug for en kirke for garnisionen, og i 1697 udarbejdede ingeniørofficeren Georg Philip Müller et forslag til den. Kirken skulle delvist finaniseres gennem de bøder, som idømtes af Højesteret.
Grunden til kirkebyggeriet blev skænket af kong Christian den 5. og lå på hjørnet af Dronningens Tværgade og Adelgade.
Efter kongens død i 1699 blev det besluttet at kirken i stedet skulle opføres ved Sankt Annæ Plads. Her var man tættere på det kapel, som i nogle år havde ligget i resterne af det nedbrændte Amalienborg Slot, og som tidligere havde tjent som kirke for garnisionen.
Den skulle også bygges større end oprindeligt tænkt, og man fik generalbygmester Wilhelm Friederich von Platen til at lave nye tegninger. Platen havde rejst i udlandet og studeret barokbygninger i Frankrig og Italien.
Det monumentale kirkerum i to etager blev udført i nederlandsk barokstil.
Alteret blev udført i norsk marmor og bærer kong Frederik den 4.s monogram, fordi kirken blev indviet i hans regeringstid i 1706.
Ved indvielsen hed kirken Den Herre Zebaoths Kirke efter navnet på hærskarernes Gud i det gamle testamente. Først i 1921 blev Garnisons Kirke det officielle navn.
Kirken var først og fremmest opført for garnisonen, men blev efterhånden også brugt af beboerne i Frederiksstaden.
I hjørnerne på den korsformede kirke, blev der i 1860 tilføjet to bygninger, der fungerede som skriftestole. De bruges i dag som præsteværelse og kontor.
I 1785 fik kirken et ligkapel, som er fornyet flere gange. Det nuværende er tegnet af arkitekten Ludvig Knudsen.
Der blev i starten holdt gudstjenester på både dansk og tysk, men kong Frederik den 6. besluttede at byens tyske menighed skulle høre til Christians Kirke på Christianshavn.
Oprindeligt lå der en kirkegård i tilknytning til kirken, og den udfyldte en del af trekanten mellem Store Strandstræde og Norgesgade (i dag: Bredgade).
I første halvdel af 1700-tallet blev der dog anlagt en større kirkegård (Garnisons Kirkegård) udenfor Østerport.
Kirkegården ved kirken blev sløjfet i 1851 da det blev forbudt at foretage begravelser inde i byen.
I 1900 blev der dog gjort en undtagelse fra forbuddet, da komponisten J. P. E. Hartmann blev begravet i sin hustrus grav udenfor kirken.
Rundt om kirken er der til gengæld opsat mindeplader og -sten for fremtrædende personer. Det gælder f.eks. kunstmalerne J. Th Lundbye og C. W. Eckersberg (herover).
På kirkegården er der et monument over de faldne i 1. Verdenskrig (herunder). Det har titlen “En af de mange” og er udført af billedhuggeren Ausa Hofman-Bang. Monumentet blev opstillet i 1934.
I 1856 blev der som nabo til kirke oprettet et kloster for Sankt Joseph Søstrene, der kom til Danmark fra Frankrig. En mindeplade fortæller om historien.
