Die Geschichte der Kirche zum Heiligen Karl Borromäus ist untrennbar mit der Entstehung des Wiener Zentralfriedhofes verbunden. Bereits im November 1863 hatte der Wiener Gemeinderat nach langen Diskussionen die Errichtung eines zentralen Friedhofes für alle Konfessionen beschlossen und hierfür 1869 ein erstes Areal in Simmering angekauft. 1870 schrieb man einen Wettbewerb für den Friedhof aus, der von den damals in Frankfurt tätigen Gartenarchitekten Karl Jonas Mylius und Alfred Friedrich Bluntschli gewonnen wurde; 1873 begann man mit der Realisierung des Projektes, am 1. November 1874 wurden bereits die ersten Teile des Wiener Zentralfriedhofes Ihrer Nutzung übergeben.
Schon im ursprünglichen Plan war eine Friedhofskirche in der Achse der älteren Gruftarkaden vorgesehen, die aber aus wirtschaftlichen Gründen zunächst nicht realisiert wurde. Erst 1899 schrieb man einen diesbezüglichen Wettbewerb aus, den der damals erst 27-jährige Architekt Max Hegele gewann. Von ihm stammt der gesamte Entwurf der axialen Anlage, vom monumentalen Friedhofstor mit den Pylonen (heute: Tor 2) bis zum Kirchengebäude mit den seitlich anschließenden Columbarien („Gruftarkaden“). Mit einigen Jahren weiterer Verzögerung wurde die Kirche 1906–11 errichtet.
Die Sanierung, mit welcher Wehdorn Architekten als Generalplaner beauftragt waren, umfasste ebenfalls das Gesamtensemble. Aus finanziellen Gründen erfolgte sie jedoch in drei Bauphasen, wobei man mit der Friedhofskirche begann.
Wer heute die Kirche betritt, kann sich nicht mehr vorstellen, dass die Bausubstanz noch vor wenigen Jahren von bestandsgefährdeten Schäden gekennzeichnet war: Im Besonderen drohten sich die vier seitlichen Türme vom zentralen Mittelbau zu lösen. Zuerst erfolgte daher die statisch-technische Sanierung, wobei die teilweise bis zu 1,8 m dicken Fundamentmauern mittels Hochdruck-Bodenvermörtelung unterfangen werden mussten. Über den Emporen konnte im ehemaligen Deckenaufbau eine bewehrte Stahlbetonplatte eingebracht werden, die wie ein Ringanker Emporen und Türme wieder an die mittlere Kuppel zurückverhängt.
Erst dann konnte die eigentliche Restaurierung beginnen. Prunkstück der Arbeiten war die Rekonstruktion des durch Kriegseinwirkung zerstörten Kuppelmosaiks in der originalen Technik, bei der rund 22.000 Einzelteile in mühsamer Kleinarbeit wiederhergestellt und zu einem goldenen Strahlenkranz mit Sternen auf blauem Untergrund zusammengefügt wurden. Jeder einzelne der Mosaik-Teile ist Handarbeit. Die Technik wird als Zwischenglas-Mosaik bezeichnet, das heißt – vereinfacht ausgedrückt – dass Blattgold zwischen zwei mundgeblasenen Glasscheiben luftdicht eingeschmolzen wird. Trotz der Feinheit des Blattgoldes beträgt das Gewicht des im Kuppelmosaik verarbeiteten Goldes mehr als zwei Kilogramm.
Zur Temperierung der Kirche wurde eine Fußboden- und Bauteilheizung nach modernsten ökologischen Gesichtspunkten installiert, eine Brandmelde- und Alarmanlage errichtet und unter der Hauptstiege eine von außen zugängliche WC-Anlage eingebaut. Ein neu errichteter Aufzug ermöglicht die barrierefreie Erschließung des gesamten Gebäudes.
Im Anschluss an die Restaurierung des Kirchengebäudes wurde als zweite Bauphase die Sanierung der Columbarien in Angriff genommen, die das Kirchengebäude beiderseits flankieren. Wie die Kirche, waren auch die Columbarien nach mehr als einhundertjähriger Bestandsdauer vom Substanzverbrauch, besonders aber von aufsteigender Grundfeuchte, gezeichnet.
Als dritte und letzte Bauphase folgte die Sanierung der Außenanlagen, im Besonderen die Restaurierung der Torbauten und die Erneuerung der auf das Kirchengebäude zuführenden Baumallee.