Nenápadná, přesto výrazná stavba u mikulovského nádraží nese v sobě několik vrstev dějin. Kostel byl vystavěn roku 1903 v pozdně-historickém novogotickém slohu z iniciativy obchodníka Josefa Johanna Kreimla pro potřeby místní německé evangelické komunity. Většinu stavebních nákladů pokryla evangelická Nadace Gustava Adolfa a hotový kostel byl vysvěcen 15. listopadu 1903 s patrociniem svatého Mikuláše.

Ke sboru patřil i tehdejší starosta Mikulova Dr. Emil Just, jehož jméno si zaslouží připomínku. V době nacistické persekuce bránil deportacím Židů a Romů do koncentračních táborů – za to byl poslán na východní frontu, kde zahynul. Němečtí evangelíci kostel užívali až do roku 1945, kdy bylo německojazyčné obyvatelstvo nuceno město opustit.

Po válce kostel chátral. O jeho správu se přihlásila Českobratrská církev evangelická, jejíž členové se zde začali scházet k bohoslužbám společně s evangelíky augsburského vyznání. Přestože o objekt usilovali dlouhodobě, formálně jej získali teprve v roce 1958. Vedle nich zde v různých obdobích sloužily mše také Církev československá husitská a Evangelická církev metodistická.

Zásadní obrat přišel v roce 1988, kdy objekt získala Olomoucko-brněnská eparchie České pravoslavné církve. Nově vzniklá Pravoslavná církevní obec v Mikulově pak do roku 1995 přistoupila k rozsáhlé revitalizaci stavby pro potřeby pravoslavného ritu. Slavnostní vysvěcení chrámu provedl dne 7. prosince 1997 tehdejší olomoucko-brněnský biskup Kryštof.

Budova samotná je jednolodní stavbou navženou architektem Trtilkou. Vyrůstá z režných cihel a tesaného kamene a dominuje jí mohutná hranolová věž v čelním průčelí – typický prvek novogotické architektury sklonku 19. a počátku 20. století. Původní malířskou výzdobu s raně křesťanskými motivy vytvořil Joža Uprka. Po přeměně kostela na pravoslavný chrám ji částečně restauroval Nikos Armutidis, který zároveň doplnil některé malby nové.

V době rekonstrukce blízké rychlostní komunikace hrozilo, že vibrace naruší statiku historické stavby – uvažovalo se dokonce o jejím stržení. Od tohoto záměru bylo nakonec upuštěno a místo demolice byly posíleny základy i bezprostřední okolí budovy. Celková renovace objektu, která probíhala intenzivněji za přispění Evropské komise, Okresního úřadu v Břeclavi, Městského úřadu v Mikulově a Památkového úřadu Brno, byla dokončena v roce 1997 pod vedením Vojtěcha Příbramského z Mikulova.

Dnes chrám svatého Mikuláše spravuje Pravoslavná církevní obec v Mikulově a zůstává jediným pravoslavným chrámem v okrese Břeclav. Pro návštěvníka jde o místo, kde se střetávají dvě různé liturgické tradice i celé jedno dramatické století evropských dějin – vše vtěsnané do střídmé novogotické budovy u vlakového nádraží.