Bland borgarna som flyttade till Karlskrona fanns många tyskar. Med Hans Wachtmeister i spetsen fick de tillstånd att bygga en egen kyrka och byggnaden har därför även kallats Tyska kyrkan. Ritningarna till denna rundkyrka gjordes av Nicodemus Tessin d.y. efter italienska förebilder. Bygget påbörjades år 1697 och kyrkan invigdes år 1709, men var då ännu ofullbordad. Träkupolen var provisorisk och portiken mot torget saknades. Efter stadsbranden 1790 stod bara murarna kvar som ruiner. Det enda man hann få ut var de två ljuskronorna i mässing från 1722 och minnestavlan krönt med kyrkan i relief från 1789. Dessa hänger ännu idag i kyrkan. 

Kyrkorummet återuppbyggdes efter Tessins ritningar men kupolen gjordes lägre. Den nya kupolen ritades i nyklassicistisk stil och takmålningen lurar ögat och får kupolen att verka högre än vad den är. Målning och träskulpturer utfördes av Johan Törnström. Vid återinvigningen 1802 fick kyrkan namnet Fredrica Dorothea Wilhelmina efter Gustav IV Adolfs drottning. Efter kungens avsättning och kungafamiljens landsförvisning fick den sitt nuvarande namn.