Um die Mitte des 19. Jahrhunderts begann der rasante Aufstieg Stuttgarts zur Großstadt. Auffällig erscheint in diesem Zusammenhang die wachsende Bedeutung der katholischen Bevölkerungsminderheit. Zwischen 1807 und 1862 war die Zahl der Katholiken von 140 auf 3.658 gestiegen. Ihr Anteil an der Gesamtbevölkerung hatte sich damit von 0,6 % auf 8,7 % erhöht. In den folgenden Jahrzehnten sollte sich dieser Trend fortsetzen.
Mit dem Wachsen der Gemeinde stellte sich immer dringlicher die Notwendigkeit zu einem Kirchenneubau. Bislang stand den Stuttgarter Katholiken lediglich die von 1808 bis 1811 errichtete Eberhardskirche in der Königsstraße zur Verfügung. Diese war nicht nur zu klein geworden, auch entsprach ihre architektonische Gestaltung nicht mehr den Vorstellungen der Zeit. Und so wandte man sich im November 1857 mit einer Bittschrift an den König. Die Hoffnung, der Württembergische Staat würde die Errichtung eines Neubaus übernehmen, wurde jedoch enttäuscht. Zwar wurden Zuschüsse in Aussicht gestellt, doch sollte die Verantwortung für die Finanzierung und Realisierung des Projektes im Wesentlichen bei der Gemeinde selbst liegen.
Die Beschaffung der finanziellen Mittel erwies sich in der Folge als eine überaus zähe und langwierige Angelegenheit. Um die Bemühungen zu forcieren, kam es 1862 zur Gründung des „Vereins für Erbauung einer neuen katholischen Kirche in Stuttgart“. Dem Verein gelang es, Mitglieder aus allen gesellschaftlichen Schichten zu gewinnen. Zudem organisierte er Benefizveranstaltungen wie Konzerte, Tombolas und eine Lotterie.
Als Bauplatz für die neue Kirche war zunächst der Alleenplatz im Bereich des späteren Stadtgartens angedacht. Diese Planung zerschlug sich jedoch, da die Stadt an der Stelle andere Bauprojekte verfolgte. Daraufhin überließ König Karl 1864 dem Kirchenbauverein unentgeltlich ein etwas weiter westlich gelegenes Grundstück nahe dem Hoppenlaufriedhof. Doch auch hier sollte der Kirchenneubau letztendlich nicht errichtet werden.
1865 entbrannte eine Diskussion um die Finanzierbarkeit der bisherigen Planungen. Auf der Generalversammlung des Kirchenbauvereins am 24. März 1866 fiel daher die Entscheidung, das Projekt neu auszurichten. Der Neubau sollte nun kleiner und damit kostengünstiger werden. Überdies sollte er die alte Eberhardskirche nicht mehr ersetzen, sondern als zweite katholische Pfarrkirche fungieren. Der ursprünglich vorgesehene Abbruch von St. Eberhard war damit vom Tisch. Angesichts der Lage von St. Eberhard im Nordosten der damaligen Stadt erschien es angebracht, die neue Pfarrkirche in einem der sich gerade erst entwickelnden südwestlichen Stadtteile zu errichten. Und so kam man mit der Stadt überein, das vom König überlassene Grundstück am Hoppenlaufriedhof gegen einen Bauplatz auf den Furtbachwiesen an der Böblinger Straße (1890 umbenannt in Tübinger Straße) einzutauschen.
Nachdem die Bauplatzfrage endlich geklärt war, schrieb man 1869 einen nichtöffentlichen Architekturwettbewerb aus. Das Ergebnis war ernüchternd. Eingereicht wurden lediglich zwei Entwürfe, die beide nicht in vollem Umfang die geforderten Kriterien erfüllten. Daraufhin beauftragte man den Stuttgarter Architekten Joseph von Egle (1818-1899), der selbst ein langjähriges Mitglied des Bauvereins war, einen dritten Entwurf zu erarbeiten. Nach der Prüfung durch die Bauräte Georg von Morlok (1815-1896) und Josef Schlierholz wurde Egles Entwurf auf der Generalversammlung des Kirchenbauvereins am 31. März 1871 zur Ausführung bestimmt. Bereits drei Monate später, am 2. Juli, erfolgte die Grundsteinlegung.
Die ursprünglich veranschlagte Bauzeit von vier Jahren wurde deutlich überschritten. Ein Grund hierfür war der wenig geeignete Bauplatz, bestand der Untergrund doch aus einer weichen, acht Meter starken Lehmschicht über wasserdurchtränktem Sand. Egle sah sich daher gezwungen, ein ebenso aufwendiges wie kostspieliges Fundament aus Portland-Zement anzulegen. Weitere Probleme, mit denen man sich während der Bauausführung konfrontiert sah, waren die in der Zeit generell sehr hohen Baupreise und der Mangel an Handwerkern. Doch schließlich konnte am 12. November 1879 der fertige Bau in Anwesenheit des Königs durch Bischof Joseph von Hefele auf das Patrozinium „Mariä Heimsuchung“ geweiht werden.
Dem Zuschnitt des Baugrundstücks folgend wurde die Marienkirche parallel zur Böblinger Straße mit der Hauptfassade nach Norden zum Stadtzentrum hin ausgerichtet. Ein großer, dreieckig zugeschnittener Vorplatz setzte den allseitig freistehenden Bau würdevoll in Szene. Leider erscheint die städtebauliche Situation heute durch die von 1959 bis 1962 errichtete Paulinenbrücke stark beeinträchtigt.
Für die architektonische Gestaltung wählte Egle die Formen der deutschen Gotik des 13. und 14. Jahrhunderts. Als Hauptvorbild diente die zwischen 1235 und 1283 errichtete Elisabethkirche in Marburg an der Lahn. Ihr Einfluss zeigt sich insbesondere in der Anlage der Doppelturmfassade sowie in der Konzeption des Langhauses als Halle mit breitem Mittelschiff und relativ schmalen Seitenschiffen. Auf die Liebfrauenkirche in Trier (ca. 1230-1260) oder die Katharinenkirche in Oppenheim (ca. 1262-1340) verweisen hingegen die beiden diagonal gestellten Seitenkapellen, die im Anschluss an das Querhaus den Chor flankieren. Das Innere der Marienkirche präsentiert sich dank der schlanken, die Sicht kaum behindernden Rundpfeiler als weiter, übersichtlicher Einheitsraum. Das Querhaus erweist sich dabei für die Raumwirkung von untergeordneter Bedeutung. Ausschlaggebend hierfür sind die dort eingefügten Sängeremporen. Der Bereich unter der westlichen Empore bildet eine zum Hauptraum hin geöffnete Kapelle. Der Bereich unter der östlichen Empore hingegen ist durch eine Mauer verschlossen und dient als Sakristei.
Egles Gestaltung war in hohem Maße dem – bereits auf das 20. Jahrhundert vorausweisenden – Gedanken konstruktiver Ehrlichkeit und Wahrhaftigkeit verpflichtet. Dementsprechend blieb die Marienkirche nicht nur außen, sondern auch im Inneren unverputzt. Die aus gelblichem Sandstein gefügten Mauern, Pfeiler und Bögen sollten ihre Materialität offen zeigen. Dasselbe galt für die in Backstein ausgeführten Gewölbekappen. Gleichwohl sollte nicht der Eindruck eines Rohbaus entstehen. Daher betonte und bereicherte man die architektonische Struktur durch direkt auf der Steinoberfläche ausgeführte ornamentale Malereien.
Der Hierarchie der Räume entsprechend waren die ornamentalen Malereien im Hauptchor und in den beiden Nebenchören besonders üppig. Zusätzlich ausgezeichnet wurden die drei Chorräume durch einen kunstvollen, figürlich gestalteten Fensterzyklus. Die an mittelalterlichen Vorbildern orientierten Entwürfe stammten von dem Wiener Maler Johann Klein (1823-1883). Die Ausführung erfolgte in der Tiroler Glasmalerei- und Mosaikanstalt Innsbruck.
Eine bemerkenswerte Ergänzung erfuhr die Ausstattung der Marienkirche 1889/90. Auf Initiative von Egle und Stadtpfarrer Gebhard Schneider (1826-1909) hatte man den Maler und Benediktinerpater Gabriel Wüger (1829-1892) beauftragt, unterhalb der Fenster des Langhauses eine friesartig angelegte Folge von Kreuzwegdarstellungen zu schaffen. Wüger war einer der Hauptvertreter der Beuroner Schule, die mit ihrem strengen, an altägyptischen, altgriechischen und byzantinischen Vorbildern orientiertem Stil ein modernes Gegenmodell zu der sentimentalen Kunst der Spätnazarener vertrat. Die Kreuzwegdarstellungen der Marienkirche fanden weit über Stuttgart hinaus Beachtung. Zur Bekanntheit beigetragen haben vor allem die großformatigen Lichtdruck-Reproduktionen, die der Theologe Paul Keppler (1852-1926) zusammen mit einem erläuternden Text 1891 publizierte. Kepplers Werk erlebte bis 1926 fünf Auflagen.
Während der Bombardements des Zweiten Weltkrieges wurde die Marienkirche schwer getroffen. Mit dem Gros der Innenausstattung gingen auch die Klein‘schen Fenster und die Beuroner Kreuzwegdarstellungen verloren. Das Äußere wurde weitgehend in ursprünglicher Form wiederhergestellt. Im Inneren wiederum sah man davon ab, die zerstörten Gewölbe des Langhauses und des Querhauses zu rekonstruieren. Man beließ – als sichtbares Zeugnis des Krieges – die erhaltenen Gewölbeansätze, zog darüber aber eine hölzerne Flachdecke ein.
1960 erhielt der Chor neue, zum Teil figürlich gestaltete Farbfenster nach Entwürfen von Otto Habel (1922-1996). Es sollte nicht der einzige Beitrag Habels zur Ausstattung der Marienkirche bleiben. 1963 schuf der Künstler einen Kreuzwegzyklus in Form von 14 hochformatigen Mosaiktafeln. 1970 folgten die abstrakten Farbfenster des Langhauses.
Zwischen 1999 und 2010 wurde das Äußere der Marienkirche aufwendig saniert. Eigentlich sollte sich eine Innenraumsanierung anschließen. Doch das Vorhaben wurde im Hinblick auf die dramatisch gesunkene Zahl der Gottesdienstbesucher zurückgestellt. Dies wiederum gab den Anstoß, die Rolle von St. Marien als Innenstadtkirche neu zu überdenken. Das Ergebnis war das zusammen mit dem Verein Stadtlücken e. V. erarbeitete Konzept „St. Maria als“, das 2017 in die Tat umgesetzt wurde. Dieses Konzept sah vor, den Kirchenraum nicht mehr nur für gottesdienstliche Zwecke zu nutzen. Vielmehr waren die Menschen und Institutionen im unmittelbaren städtischen Umfeld aufgerufen, St. Marien auf unterschiedlichste Weise zu einem Ort der Begegnung und des Austausches zu machen. Die Bandbreite der seitdem durchgeführten Veranstaltungen reicht von der Kunstinstallation über die Tanzperformance bis zum Kräuterworkshop. 2021 wurde „St. Maria als“ mit dem Innovationspreis des Zentrums für angewandte Pastoralforschung ausgezeichnet.