Первый храм в Штутгарте был устроен с прибытием сюда для бракосочетания с Королём Вюртемберга Вильгельмом I (1771-1864) Великой Княжны Екатерины Павловны (1788-1819), дочери Императора Павла I, в первом браке Принцессы Ольденбургской. Это была походная церковь, которая была помещена в так называемом Fürstenbau, теперь уже не существующем. Одновременно с будущей Королевой прибыл причт. После кончины в 1819 году Королевы, эта церковь, вероятно, была перенесена в выстроенный над её могилой особый храм на Ротенберге, где с 1824 по 1889 год постоянно проходили богослужения.
В связи с отдалённостью Ротенбергской церкви в 1842 году русский посланник при Вюртембергском дворе, князь А. М. Горчаков ходатайствовал об устройстве особой походной церкви при российской миссии. Храм был устроен. При этом причт продолжал проживать на Ротенберге. Этот походный храм с 1846 года посещала Великая Княжна, впоследствии Королева Вюртемберга Ольга Николаевна (1822-1892).
В 1854 году Император Николай I в подарок своей дочери передал всё необходимое для устройства собственной домовой церкви, которая первоначально помещалась во дворце кронпринца. В 1864 году, после того, как Ольга Николаевна стала Королевой, храм был перенесён в Большой дворец. Церковь при миссии была закрыта в 1854 году.
После смерти в 1892 году Королевы Ольги Николаевны, дворцовая церковь была перенесена в королевскую виллу «Berg» (Villastrasse), которая в тот период принадлежала Великой Княгине Вере Константиновне (1854-1912), бывшей в замужестве за Герцогом Евгением Виртембергским (1846-1877). На вилле храм помещался в двух небольших комнатах верхнего этажа.
В 1894 году, по инициативе Герцогини Веры Константиновны и ходатайству посланника Э. К. Коцебу, Император Александр III утвердил проект постройки нового отдельного храма во имя святителя и чудотворца Николая на небольшой площади, выходящей на Hegelstrasse.
Место было предоставлено городским управлением за 12 000 марок. Закладка храма состоялась 6 (18) мая 1895 года. Автором проекта является немецкий архитектор Людвиг Айзенлор. На строительство из казны было выделено 75 000 рублей.
6 (18) декабря 1895 года храм был освящён протоиереями Фефилом Кардасевичем, Павлом Румянцевым и Арсением Вольским. Сюда был перенесен иконостас и прочие церковные принадлежности с виллы «Berg».
С началом Первой мировой войны церковь была закрыта. В 1922—1930 годах храм находился в юрисдикции Управляющего русскими приходами в Западной Европе Русской Православной Церкви. С переходом митрополита Евлогия (Георгиевского) в Константинопольский Патриархат, в Западноевропейском экзархате русских приходов. В 1938 году храм был передан «Епархии православных епископов Берлина и Германии» Русской Православной Церкви Заграницей.
В ночь с 12 на 13 сентября 1944 года храм был сильно повреждён в результате бомбардировки: колокольня и купол обрушились, убранство и утварь сгорели. В начале 1950-х годов с помощью городских властей здание было восстановлено в прежнем виде.
В начале 1970-х годов иконописцем Николаем Шелеховым был воссоздан иконостас, а в конце 1980-х годов храм был расписан.
В настоящее время храм относится к Германской епархии Русской Православной Церкви Заграницей. Имеет статус памятника культуры. Настоятель — протоиерей Илья Лимбергер, в общине состоит свыше 1000 прихожан. Организован хор.