Kompleks dzisiejszej cerkwi powstał w 1914 r. jako miejskie krematorium. Obiektowi nadano formy nawiązujące do architektury średniowiecznej, neogotyckich kształtów całości i neoromańskich detali.
Zmiana dotychczasowej wielowiekowej praktyki postępowania z ciałami zmarłych podyktowana była względami zarówno higienicznymi jak i postulatem ograniczenia przestrzeni potrzebnej dla funkcjonowania cmentarzy. Nowoczesność i korzyści wynikające z takiego podejścia sprawiły, że idea pochówków krematoryjnych zyskiwała sobie szybko licznych zwolenników, mimo oporu tradycjonalistów. Funkcjonowanie gdańskiego krematorium przerwał rok 1945 i miało minąć jeszcze wiele lat, zanim do idei powrócono i wzniesiono w Gdańsku nowe krematorium.
W latach powojennych obiekt kilkukrotnie zmieniał użytkowników. Bezpośrednio po wojnie znajdował się w posiadaniu Centralnego Zarządu Cmentarzy, myślano nawet o wznowieniu jego funkcji kremacyjnej, spotkało się to jednak nie tylko z brakiem zainteresowania, ale i jednoznacznie negatywnym nastawieniem nowej, polskiej ludności Gdańska. Biorąc pod uwagę konotacje wyrazu "krematorium" w powojennej polskiej kulturze nastawienie takie nikogo nie powinno dziwić.
Kompleks przekazano zatem w dzierżawę parafii ewangelicko-augsburskiej, a po kilku latach gdańskiej wspólnocie prawosławnej.
Obecność osób wyznania prawosławnego i obiektów religijnych tego wyznania w Gdańsku zaczyna się jeszcze w XVIII w., kiedy to przy Długich Ogrodach powstał pałac konsulów rosyjskich, w którym utworzono kaplicę pod wezwaniem, które nosi gdańska cerkiew do dziś, tj. św. Mikołaja. Kaplica ta służyła nie tylko rosyjskim dyplomatom, ale również coraz liczniejszej rosyjskiej kolonii, a także bawiącym przejazdem w Gdańsku wyznawcom prawosławia. Rewolucja rosyjska spowodowała napływ do Miasta licznych emigrantów politycznych, uchodzących przed bolszewickim terrorem. Początkowo gromadzili się oni w kaplicy w konsulacie, od momentu jednak przekazania go nowej władzy radzieckiej, zmuszeni byli do znalezienia sobie nowego miejsca. Odtąd prawosławna kaplica, ciągle nosząca imię św. Mikołaja, znajdowała się w kamienicy przy ul. Garncarskiej. Po wojnie ośrodek gdańskiego prawosławia mieścił się w kamienicy przy ul. Sienkiewicza we Wrzeszczu. Od 1953 r. parafia prawosławna użytkuje budynek kaplicy krematoryjnej przy Traugutta, a od roku 1983 całość pokrematoryjnego kompleksu.
Remont i adaptacja przeprowadzana etapami od lat 50. i trwające właściwie do dnia dzisiejszego uczyniły z budynku bardzo interesującą architektoniczną hybrydę, powstałą z opatrzenia bryły utrzymanej w stylistyce zachodnioeuropejskiego średniowiecza w rusko-bizantyjską dekorację. W ten sposób dzisiejsza cerkiew jest jednym z widomych dowodów procesów stapiania się kultur na terenie Gdańska, a jej patron, św. Mikołaj, jako patron pojednania zwaśnionych przed tysiącem lat odłamów chrześcijańskich, czyni z niej jeden z pomników gdańskiej wielokulturowości.
