Karlskrona stad och örlogsvarv grundades 1679, och 1681 bildades Karlskrona Amiralitetsförsamling. Placeringen av församlingskyrkan, på Trossös sydöstra udde, var fastställd i den första stads- och befästningsplanen från år 1683.
Det är inte säkerställt vem som ritat kyrkan men det är möjligt att arkitekten var generalkvartermästaren Erik Dahlbergh. Timret till kyrkan fraktades från Riga, men på 1680-talet tillhörde staden Sverige och var då rikets största stad med 100 000 invånare. 20 september 1685 invigdes kyrkan och fick då namnet Ulrica Pia, efter Ulrika Eleonora den äldre.
Ursprungligen låg kyrkan innanför den slutningsmur som finns mellan den civila staden och örlogsbasen med varvet. På 1800-talet revs bland annat muren vid kyrkan och ersattes av en mindre bastant mur mellan kyrkan och Örlogsbasen. I kvarteret norr om Varvsgatan finns rester kvar av den ursprungliga muren. Det finns också kvar en stor slutningsmur kring Karlskronavarvet.
Amiralitetskyrkan var liksom Storkyrkoförsamlingens kyrka på Drottninggatan tänkt att vara tillfällig och bli ersatt av en stor stenkyrka. Efter många olika ritningar och diskussioner lades grunden till en stenkyrka vid Amiralitetsklockstapeln på midsommarafton 1760. Till kungens ära skulle kyrkan få namnet Adolf Fredrikskyrkan. Ritningarna på denna kyrka av Carl Johan Cronstedt finns på två plåtar till kopparstick som ägs av församlingen. Pengarna tröt dock och efter 20 år nådde murarna bara en höjd av 14 alnar (drygt 4 meter). Efter ett kungligt brev lades hela byggprojektet ned och kyrkobygget blev en ruin.
Åren 1822-1823 genomgick träkyrkan en omfattande renovering, bland annat tillkom lanterninen i mittkvadraten.
Kring år 1850 blev det till sist uppenbart att stenkyrkan aldrig skulle bli av. Resterna av bygget revs och istället väcktes tanken att om det inte var möjligt att få en stenkyrka så kunde ju träkyrkan åtminstone se ut som en stenkyrka likt Fredrikskyrkan och Trefaldighetskyrkan. Därför byttes ytterpanel, kyrkan målades gul och gavs arkitektoniska detaljer i barockstil. Kyrkan förföll sedan en tid, men reparerades 1864.
År 1875 började åter frågan om en stenkyrkan debatteras, en debatt som fortgick i 30 år då den fick ett slut när Sjöförsvarsdepartementet avslagit församlingens begäran om medel. Efter det fick församlingen istället pengar, som kungen beviljat, till en upprustning av kyrkan som sedan genomfördes 1908-1909. El drogs in och kyrkan fick ett nytt plåttak. En förhall uppfördes framför norra gaveln 1845, ritad av C.E. Wallenstrand. Denna togs bort vid stadsarkitekten S. Ulléns restaurering 1943-1949. 1958 byttes plåttaket ut till ett koppartak. Följande år fick kyrkan en ny trappa vid huvudingången i kalksten från Öland i samma stil som den tidigare med ursprungliga trappräcken.
År 1974 beslöt ägaren Fortifikationsverket att exteriören skulle rödmålas för att kyrkan skulle få sin ursprungliga karaktär. Riksantikvarieämbetet var emot detta, men kyrkan rödmålades ändå 1985.
Kyrkan är uppförd helt i trä, rödmålad och i formen av ett grekiskt kors, byggd på en sockel av stora stenblock.
I exteriören framträder mittpartiet som en kubisk byggnadskropp, omkring 20x20 meter, med säteritak och krönande oktogon med karnisformad huv. Korsarmarna är lägre och skjuter fram som förhallar; de har valmade yttertak.
De träpanelade fasaderna indelas genomgående av pilastrar. Fönstren är rundbågade med rektangulära omfattningar. Ingångar finns i norr, väster och söder (raktäckta dubbeldörrar mitt på korsarmsgavlarna). Koret är placerat i östra korsarmen, tillsammans med sakristian.
Inuti är träet ljusblått och ljusgrönt, vilket för tankarna till havet. Interiörens fyra kraftiga träpelare, förbundna med vågräta bjälkar, bär upp mittpartiets takkonstruktion. Genom pelarna bildas en mindre mittkvadrat som täcks av ett högre plafondtak (ej ursprungligt, förhöjningen tillkom troligen 1822-23), samt en omgång med plana trätak.
Södra och norra korsarmarna har läktare och plana innertak av trä. Orgelverket i väster är placerat i en tunnvälvd nisch. Koret täcks av ett tryckt trätunnvalv.
Väggarna är klädda med träpanel. Kyrkans ursprungliga övre läktare nedtogs vid arkitekt Theodor Wåhlins restaurering 1908-1909. Vid Ulléns restaurering tillkom bland annat korsarmarnas vestibuler och nya yttertrappor i kalksten mot ingångarna i söder och väster.
Mellan åren 1943 och 1949 leddes en restaurering av dåvarande stadsarkitekten S. Ullén. Denna restaurering gav kyrkan en ljusare interiör, värmeledningar och innebar att dekoreringen i taket övermålades. Nu gavs också bänkarna en mörkgrå färg, en färg som senare gjordes något ljusare.
Mellan ytterväggarna och innerväggarna döljer sig ett 20 cm stort hålrum. Innerväggen lär inte blivit helt färdigställd till förrän 1691, sex år efter invigningen. Detta skapade problem för präster och besökare på vinterhalvåret. Problemen kvarstod dock, även när innerväggen var installerad och en grön pottugn murad