Im Februar 1933 erfolgte der erste Spatenstich für die Clemenskirche und das angebaute Clementinum – ein kleines Kloster für den Orden der Redemptoristen. Architekt war Regierungsbaumeister Hugo Schlösser, der mehrfach an Kirchenbauten in der Diözese beteiligt war.
Nach einer Bauzeit von nur acht Monaten wurde die Kirche am 15. Oktober durch Bischof Dr. Johannes Baptista Sproll eingeweiht. Patron der Kirche ist der Hl. Klemens-Maria Hofbauer.
Bis 1958 war die Gemeinde rechtlich eine Filiale der Mutterkirche St. Elisabeth, dann wurde St. Clemens zu einer eigenen Stadtpfarrei erhoben.
Im den Jahren 1968/69 fand als Folge des II. Vatikanischen Konzils ein Umbau statt, um die Richtlinien des Konzils umzusetzen. Die Hl. Messe sollte der Priester nicht mehr mit dem Rücken zur Gemeinde und nicht mehr in lateinischer Sprache, sondern auf Deutsch feiern. Im Wesentlichen wurde ein neuer Altar erbaut, der in die Mitte des Chorraumes gerückt war.
Zum 70-jährigen Jubiläum der Kirche im Oktober 2003 erfolgte eine größere Innenrenovierung nach Plänen des Architekturbüros „Kreuz und Kreuz“. Mit einbezogen in die Renovierung war das Landesdenkmalamt, da Kirche und Kloster unter Denkmalschutz stehen. Vorgabe war es, die Renovierung so durchzuführen, dass der Zustand der Kirche von 1933 soweit möglich wieder erreicht wird.
Die Architektin Frau Dr. Kreuz führt hierzu in der Festschrift aus: „Die Architektur der Clemenskirche ist nicht nur geprägt durch die Redemptoristen, sondern auch typisch für die dreißiger Jahre. Ihre Gestaltung stellt die Struktur des regionalen Materials – eingefärbter Kalkputz, Betonwerkstein, Cannstatter Travertin, Pflasterklinker, Kupferblech, Fichtenholz – heraus. Sie zeigt die für diese Zeit kennzeichnende Wärme in der Farbigkeit der Rumschale und der Außenhaut.“
Und Sie führt weiter aus: „Die Redemptoristen haben mit Hugo Schlösser eine Kirche mit menschlichem Maßstab geplant, einfach und schlicht in ihren Materialien, dennoch elegant in ihren Proportionen – mit den schlanken Pfeilern, den in Dreiergruppen angeordneten hohen Rundbogenfenstern und der Dynamik der auf das Kreuz und Altar hinführenden Decke“.
Die Schaffung neuer Wohngebiete in Stuttgart-Botnang verlangte auch nach neuen Kirchen in diesen Neubaugebieten: Im „Laihle“ wurde eine Kirche mit Gemeindesaal und einer Kindertagesstätte geplant. Der Bau dieses kirchlichen Zentrums erfolgte in den Jahren 1970/71 nach Plänen von Architekt Dipl. Ingenieur Fred Hummel. Am 14.12.1971 wurde die Christus-Erlöser-Kirche durch Generalvikar Dr. Knaupp geweiht.
Die Kirche ist ein einfacher Betonbau, dessen Innenraum sehr schlicht ausgestaltet ist. Sie sollte – wie eine ganze Reihe von Kirchen, die etwa zur selben Zeit in unserer Diözese entstanden – möglichst effizient und kostengünstig der rasch wachsenden Bevölkerung eine kirchliche Heimat bieten.
Im Zuge des Projekts „Aufbrechen“ des Stadtdekanats Stuttgart, mit dem die Struktur der Stadtkirche den rückläufigen Katholikenzahlen und Finanzmitteln angepasst wird, soll die Kirche in den nächsten Jahren aufgegeben und durch ein Zentrum mit sozialen Aufgaben ersetzt werden.