Im Jahre 1713 wurde die kaiserliche Residenzstadt Wein von einer furchtbaren Pestseuche heimgesucht. Der damalige Kaiser Karl VI. gelobte zum Dank für die überstandene Pestgefahr zu Ehren seines Namenspatrons Karl Borromäus ein würdiges Gotteshaus errichten zu lassen. Der Hl. Karl war ja selbst durch sein vorbildliches und aufopferndes Wirken für die Pestkranken seiner Bischofsstadt Mailand neben den Hl. Sebastian, Rochus und Rosalia zum Pestpatron der Katholischen Kirche geworden.

Auf Befehl des Kaisers erfolgte dann eine Ausschreibung zur Erstellung eines Modells für die Kirche, woran sich die drei berühmten Architekten Johann Bernhard Fischer von Erlach, Johann Lukas Hildebrand und Ferdinando Galli Bibiena beteiligten.

Nachdem das Modell Fischers den Vorzug erhielt, konnte im Jahr 1715 mit den Erdaushebungen begonnen werden. Zur Aufbringung der für den Bau nötigen geldlichen Barmittel hatten vor allem die Stände der erbländischen Provinzen und viele Private beigetragen. Ebenso beteiligten sich an diesen Leistungen Spanien, die Niederlande, Mailand, Italien und Böhmen.

Der Bau der Karlskirche dauerte 21 Jahre, nachdem am 4. Februar 1716 die feierliche Grundsteinlegung stattfand. Im selben Jahr trat der von der Hl. Agnes 1233 in Prag gegründete ritterliche Kreuzherrenorden mit dem Roten Stern mit dem Kaiser in Gespräche, was die geistliche Obsorge der Kirche betrifft. Diese wurde schließlich im Jahre 1733 durch eine kaiserliche Entschließung vom 10. November an den Orden übertragen.

Auch im hiesigen Kreuzherrenhof bestand nach dem Ordensstatut ein Armenhaus. Von dieser zeit bis zum heutigen Tag ist, mit einer provisorischen Unterbrechung, die Kirche der Obhut dieses Ordens anvertraut.