Die Geschichte des russisch-orthodoxen Glaubens in Stuttgart beginnt am 13. April 1816. An diesem Tag kam Katharina Pawlowna Romanowa, Großfürstin von Russland, als Gemahlin von Kronprinz Wilhelm, dem künftigen König von Württemberg, nach Stuttgart. Sie und ihr Hofstaat legten den Grundstein für die bis heute lebendige Gemeinde. Nach dem frühen Tod von Königin Katharina im Januar 1819 ließ König Wilhelm I. (1781-1864) für sie von Hofbaumeister Giovanni Salucci eine Grabkapelle auf dem Württemberg errichten. Diese Kapelle vor den Toren der Stadt war der erste russisch-orthodoxe Sakralraum, in dem die Gemeinde ihre Gottesdienste feiern konnte.
Da die Grabkapelle auf dem Württemberg jedoch relativ weit entfernt lag, suchte die russische Gesandtschaftskirche bereits in den 1860er Jahren alternative Räume in Stuttgart. Von 1865 bis 1892 konnte sie die von Königin Olga (1822-1892) angelegte Kapelle im Neuen Schloss nutzen. Nach deren Aufhebung standen der Gemeinde zeitweise Räume in der Villa Berg, dem Wohnsitz Herzogin Weras, zur Verfügung. Hauptkirche für die in Stuttgart lebenden Russen und Griechen war in jenen Jahren jedoch wieder die Grabkapelle auf dem Württemberg.
1894 gelang es der kaiserlich-russischen Gesandtschaft, Herzogin Wera als Führsprecherin für den Neubau einer Kirche in Stuttgart zu gewinnen. Die Herzogin unterstützte gemeinsam mit ihrem Cousin Zar Alexander III. das Bauvorhaben, das so auch zu einem Zeugnis für die enge dynastische Verbindung des württembergischen Königs- und des russischen Zarenhauses werden sollte. Wohl aus Kostengründen beauftragten die Bauherren keine Architekten aus Russland mit dem Neubau, sondern wandten sich an dasjenige ortsansässige Architekturbüro, das schon bei der Suche nach einem geeigneten Bauplatz zu Rate gezogen worden war. Eine erste Skizze aus der Feder Ludwig Eisenlohrs (1851-1931) zeigt den Kirchenbau auf dem heutigen Gelände an der Seidenstraße. Zuvor hatte man den Hegelplatz als möglichen Bauplatz in Erwägung gezogen, der allerdings von der Stadt nicht veräußert wurde. Beide Plätze hatten eine dreieckige Grundfläche, so dass die bereits angestellten Überlegungen vom Hegelplatz auf den endgültigen Standort an der Hegel- und an der Seidenstraße übertragen werden konnten.
Das erste Baugesuch wurde am 11. Juli 1894 eingereicht, die Bauarbeiten selbst begannen im Februar 1895. Bei der Grundsteinlegung am 18. Mai 1895 war der Bau bereits bis auf Sockelhöhe vorangeschritten, so dass der Grundstein am Platz unter dem künftigen Altar gelegt werden konnte. Die Kirche wurde im Dezember desselben Jahres, am Namenstag des hl. Nikolaus, eingeweiht. Es dauerte allerdings noch anderthalb Jahre, bis die Ausmalung der Räume vollendet war. Herzogin Wera stiftete der Kirche die Glocke und stellte dem Gotteshaus die kostbare Innenausstattung der russisch-orthodoxen Kapelle von Königin Olga aus dem Neuen Schloss zur Verfügung.
Die Architektur der russisch-orthodoxen Kirche stellte den Stuttgarter Architekten Ludwig Eisenlohr und sein Büro Eisenlohr & Weigle ohne Zweifel vor eine große Herausforderung. Traditionell war der Kirchenbau im ausgehenden 19. Jahrhundert an mittelalterlichen Stilformen wie der Neuromanik oder der Neugotik angelehnt. Für den Bau einer Russischen Kirche aber war das wenig passend. Eisenlohr orientierte sich für die Gestaltung des Baus folglich am russischen Kirchenbau des 17. Jahrhunderts, der durch seinen überreichen Dekor und durch pittoreske und häufig asymmetrisch angelegte Bauten geprägt war. Die Stuttgarter Kirche entsprach in Form und Größe einer russischen Dorfkirche. Sie hat einen Kirchenraum, der von einer Kuppel überwölbt wird, sowie einen Kirchturm, der sich über dem Eingang, aufgestützt auf vier Säulen, erhebt. Durch den asymmetrischen Aufbau der Anlage präsentiert sich die Kirche zum Hang und zum Tal hin mit deutlich unterschiedlichen Fassaden.
Die zentralen Räume des Kirchenbaus sind das Kirchenschiff und der Altarraum. Sie bestimmen die innere Organisation des Baus ebenso wie seine äußere Gestalt. Die beiden Hauptfassaden sind zur Hegel- und zur Kornbergstraße ausgerichtet. An beiden Fassaden finden sich der russischen Tradition entlehnte Ornamente und Schmuckformen, die den Bau im besten Sinne des Historismus ausweisen und schmücken. An den Eckpfeilern beider Fassaden etwa sind Schirinki, rechteckige, kassettenartige Vertiefungen zu sehen, und die Sandsteineinfassungen der Fenster sind in Anlehnung an russische Holzarchitektur schmuckvoll gestaltet, zudem finden sich im Bereich der Fenster Darstellungen des doppelköpfigen Adlers, des Wappentiers des russischen Zaren. An der Fassade gegen die Seidenstraße ist dem Kirchenschiff eine einstöckige Sakristei vorgelagert. Zwischen Sakristei und Glockenturm liegt eine enge Treppenhausspindel, die die Sakristei mit einem Raum im zweiten Stock des Turmes verbindet.
Auffallend und eigenwillig ist die Lösung des Eingangsbereiches der Kirche. Die Eingangstreppe ist unter dem 23,5 Meter hohen Kirchturm hindurchgeführt. Sie geleitet über zwei Treppenabsätze die Besucher in einen Vorraum im Hochparterre und von dort in den großen Kirchenraum. Der Turm der Kirche steht durch diese Wegführung auf vier gedrungenen Säulen. Durch diese gewagt scheinende Konstruktion gelang es Eisenlohr, neben dem Kirchenraum mit Kuppel auch einen Kirchturm organisch in das Ensemble zu integrieren. Die Kuppelverkleidung aus Eisenblech wurde in Anlehnung an die Architektur russischer Holzkirchen mit einer schindelförmigen Struktur geprägt. Kuppel und Turmspitze tragen vergoldete russische Kreuze.
Die Innenausstattung des Kirchenraumes ging im Zweiten Weltkrieg verloren. In der Architektonischen Rundschau von 1897 aber findet sich eine Beschreibung: „Der einschiffige Kirchenraum ist mit Gewölbeformen aus Rabitzputz überdeckt, dergestalt, dass eine mittlere flache Hängekuppel von zwei seitlichen Tonnengewölben flankiert wird. Der ganze Innenraum ist nach den Entwürfen der Erbauer über einem Marmorpaneel in charakteristische Weise reich bemalt unter ausgiebiger Verwendung von echter Vergoldung, und verfehlt nicht, einen stimmungsvollen Eindruck hervorzurufen. Zur Belebung des Inneren trägt weiter eine Sängertribüne bei, welche, über der Sakristei eingefügt, die dort befindliche sonst kahle Hochwand an passender Stelle durchbricht und belebt.“ Abbildungen zeigen die reiche ornamentale Ausmalung des Kirchenraumes, der durch den Ikonostas Königin Olgas und durch ein hohes Ziergitter vom Altarraum abgetrennt war. Der Raum wurde durch die Fenster und durch einen großen, von der Kuppel herabhängenden Kronleuchter erhellt.
Bis zum Ersten Weltkrieg stand die Kirche allen russisch-orthodoxen Gläubigen offen. Bei Ausbruch des Krieges 1914 verließen die russische Gesandtschaft und viele andere russische Staatsbürger Stuttgart, sodass der Bau – unter polizeilichem Schutz – neun Jahre geschlossen blieb. 1923 konnte die Gemeinde ihre Kirche wieder öffnen und die Schäden der langen Kriegsjahre reparieren. Im Zweiten Weltkrieg wurde der Bau zweimal von Bomben getroffen. In der Nacht vom 12. und 13. September 1944 zerstörten Bomben fast das ganze Wohnviertel um die Kirche. Der Kirchenbau brannte aus, seine Umfassungsmauern jedoch blieben erhalten. Der Wiederaufbau dauerte bis 1960, danach begann man mit den dringend notwendigen Restaurierungsarbeiten an den Fassaden und mit der Neugestaltung der Innenräume. Nach der Restaurierung der Kuppel und des Turmes 1996 bis 1998 erhielt die Kirche erstmals ein volles Geläut: Zu der erhaltenen Glocke, die Herzogin Wera 1895 zur Einweihung gestiftet hatte, kamen neun weitere Glocken hinzu.
Ludwig Eisenlohr zählte die Russische Kirche zu den wichtigsten Bauten seines Œuvres. Das Gebäude steht seit 1983 unter Denkmalschutz und wird nach wie vor von der russisch-orthodoxen Gemeinde Stuttgarts als Sakralraum genutzt.