Vorgängerbau

Bis in das 15. Jahrhundert war Karlsbad Filiale der Pfarrei Zettlitz. Eine der hl. Maria Magdalena geweihte hölzerne Kapelle dürfte sich seit der zweiten Hälfte des 14. Jahrhunderts im Zentrum auf einem Hügel in der Nähe des Sprudels befunden haben. Am 14. August 1370 erhob Kaiser Karl IV. den schon vorher bestehenden Ort Warmbad zur Königsstadt. In Zusammenhang einer Schenkung des Grafen Hieronymus Schlick wurde die Kirche 1485 erstmals urkundlich erwähnt. Über das Patronatsrecht verfügten die Kreuzherren mit dem Roten Stern. Seit 1491 war sie eine eigenständige Pfarrkirche. Eingepfarrt waren außer Karlsbad noch die Dörfer Donitz, Drahowitz, Fischern, Ober- und Untermaierhöfen sowie das zur Herrschaft Gießhübel gehörende Berghäusln. 1493 war ein Kreuzherr namens Nikolaus Pfarrer.

1518 erfolge ein Neubau in Form einer kleinen einstöckigen Fachwerkkirche. Sie war von einem Friedhof umgeben, der seit etwa 1500 als Begräbnisplatz diente. Hinter der Kirche befand sich auf höherer Trasse ein Pfarrgarten. Im 16. Jahrhundert hielt die Reformation Einzug. Bereits um 1535 soll ein Pastor in der Andreaskirche gepredigt haben. 1554 nahm der Rat offiziell die lutherische Lehre an. Bis 1624 war die Pfarrstelle mit 13 lutherischen Geistlichen in Folge besetzt. Der erste war Andreas Hampisch. Die Kirche wurde beim Stadtbrand von 1604 zerstört, jedoch kurz Zeit später wieder aufgebaut. 1605 erhielt sie vom Glockengießer Hans Wild aus St. Joachimsthal neue Glocken. Während des Dreißigjährigen Krieges wurde die Kirche erneut durch einen Brand zerstört. Der letzte Pastor Johannes Rebhun musste am 24. August 1624 auf Befehl Kaiser Ferdinand II. zusammen mit jenen Bürgern, die nicht zum Katholizismus konvertierten, das Land verlassen. Rebhun wurde 1624 Pfarrer in Culmitzsch in der Diözese Weida und starb 1675.

1628 wurde der katholische Gottesdienst gewaltsam wieder eingeführt. Viele Bürger, vor allem Frauen, konvertierten erst später. Der erste katholische Seelsorger seit der Reformation war der Augustinermönch Pater Franciscus Albinus. Auf ihn folgten abwechselnd Kreuzherren, Weltpriester und andere Ordensgeistliche. Seit 1656 war die Pfarrstelle stets mit Kreuzherren besetzt. Ab 1698 übte der Kreuzherrenorden das Präsentationsrecht gemeinschaftlich mit dem Magistrat der Stadt aus, in der Form, dass der Großmeister drei Ordenspriester vorschlug aus denen der Magistrat einen auswählte, der dann dem fürsterzbischöflichen Konsistorium präsentiert wurde.

Neubau bis zur Gegenwart

Da die alte zu klein gewordene Kirche nicht mehr den Anforderungen entsprach und wegen ihres schlechten Bauzustandes einzustürzen drohte, setzten sich 1727 der Großmeister des Kreuzordens und der frühere Dekan Franz Matthias Böhm bei Kaiser Karl VI. für einen Neubau ein. Die Pläne lieferte der Architekt Kilian Ignaz Dientzenhofer, der Ende 1729 in Karlsbad eintraf und notwendige Sondierungen durchführte. Darüber hinaus suchte Dientzenhofer nach einem geeigneteren Standort und fertigte mehrere Entwürfe an. Die mangelnde Finanzierung und Grundstücksfragen verzögerten das Vorhaben zunächst.

1732 stiftete der Bürger Lorenz Pleyer eine Summe von 4.000 Dukaten um die Anstellung eines zweiten Kaplans zu ermöglichen. Voraussetzung war, jede Woche vier Seelenmessen für den Stifter zu zelebrieren. Die Genehmigung zum Neubau erteilte Kaiser Karl VI. per Dekret am Tag vor seiner Abreise aus Karlsbad am 17. Juli 1732. Anschließend begannen am Fundament Ausgrabungen, die heiße Quellen zu Tage führten und in den Gräben Stalaktiten. Die Grundsteinlegung durch den Großmeister Franz Matthias Böhm erfolgte am 27. April 1733. Die Bauaufsicht übernahm der Polier Thomas Hansl aus Prag, der noch vor der Vollendung der Kirche starb. Weitere am Bau beteiligte waren die Schlosser Johann Kaspar Kraus und Johann Peter Hüttner, sowie der Tischler Franz Dietl. Stuckateur war Ignaz Palliari aus Prag. Die Arbeiten wurden wegen heißer Quellen die auf dem Gelände hervortraten, massiv behindert. Teilweise drohten die Dämpfe die Arbeiter zu ersticken. Die Kirche war bis 1736 fertiggestellt. Die Gesamtkosten betrugen 95.000 Dukaten, wofür größtenteils der Kreuzherrenorden aufkam, Kaiser Karl VI. steuerte einen Beitrag von 1000 Dukaten hinzu.

1756 begann der Bau eines neuen Dekanatsgebäudes. 1759 wurde die Kirche durch ein Feuer massiv beschädigt. 1763 stifte Kaiserin Maria Theresia der Kirche eine neue Turmuhr des Prager Uhrmachers Sebastian Landensberger und drei neue Glocken. Nach einer Hunger- und Pestepidemie, die den Kurort in den 1770er Jahren heimsuchte, wurden der Friedhof in der Innenstadt aufgelassen und die sterblichen Überreste teilweise in die Krypta transferiert.

Auf Geheiß Kaiser Joseph II. verlegte man den neuen Friedhof 1784 an die zu dieser Zeit noch außerhalb der Stadt liegende Andreaskirche, die seit dem Jahre 1500 bestand und 1840/1841 im Empire-Stil umgebaut wurde. Die Türme erhielten 1861 ihre Laternen, wozu Graf Joachim von Münch-Bellinghausen einen Betrag von 1000 fl. beisteuerte. 1883 schenkte der Unternehmer Heinrich Mattoni der Kirche ein großes Glasfenster. 1930 zählte die Pfarrei 25.504 Katholiken. Letzter Dechant war Adam Becker aus dem Kreuzherrenorden. Zwischen 1948 und 1950 wurde die Kirche komplett restauriert. 1958 erfolgte die Aufnahme in die staatlichen Liste der Kulturdenkmäler. Seit 2010 wird die Kirche als nationales Kulturdenkmal geführt.