Vuonna 1926 helsinkiläisten ortodoksien keskuuteen syntyi yhteisö, joka kokoontui yhteen vanhan juliaanisen kalenterin mukaisina kristillisinä juhlapäivinä. Tämä yhteisö rekisteröitiin ja nimettiin Pyhän Nikolauksen veljeskunnaksi.
Ainoa yhteisön omistama kirkollinen arvoesine oli Pyhän Nikolauksen ikoni, jonka edessä rukoiltiin. Ikoni on edelleenkin seurakunnan hallussa ja se sijaitsee Pyhän Nikolauksen kirkossa oikeanpuoleisella analogilla (kiotassa ja ilman riisaa). Veljeskuntaa yhdistävänä keskeisenä tekijänä oli tahto käynnistää Helsingissä säännölliset jumalanpalvelukset vanhan juliaanisen kalenterin mukaisesti ja kunnioittaen vanhoja kirkollisiä perinteitä. Vuonna 1923 Suomessa annettu Uskonnonvapauslaki salli esteittä perustaa uskonnollisia yhdyskuntia ja yhdistyksiä.
Yhdyskunnan perustajat Vasily Savich Sinkevich, Pavel Matveevich Moshkirev sekä Alelsandra Konstantinovna Vasiljeva lähtivät Viipuriin hakemaan keskusteluseuraa ja neuvontaa kokeneelta pastorilta isä Grigory Svetlovskilta.
Isä Gregoryn kertomuksesta selvisi, että Viipurin ortodoksien oma yhteisö on jo ehtinyt jättää perustamishakemuksensa koskien Viipurin Pokrovan yhdyskuntaa. Hänen suosituksensa oli lykätä Helsingin yhdyskunnan perustamishakemuksen jättämistä. Kun Viipurin yhdyskunnan rekisteröinti hyväksyttiin, Helsingin yhdyskunnan hakemus toimitettiin 20 allekirjoituksen kera isä Grigory Svetlovskylle hallitusinstansseille toimitettavaksi.
Rekisteröinnin jälkeen oli seurakunnalle löydettävä pappi. Isä Grigory Svetlovsky suositteli ottamaan yhteyttä kronstatilaiseen pakolaiseen –rovasti Nikolai Shtshukiniin. Ennen vallankumousta Nikolai Selvestrivich Shtshukin, syntynyt 4. elokuuta 1876, oli antautunut sotilasuralle armeijan insinöörinä. Vallankumouksen jälkeen Ortodoksisen Kirkon pahimpaan vainon aikaan 14. joulukuuta 1920 hänet oli vihitty papiksi Moskovassa.
Ensimmäiset jumalanpalvelukset Suomessa hän toimitti piikkilanka-aidan toisella puolella Inon linnakkeen pakolaisleirillä. Myöhemmin hän toimi opettajana pakolaiskoululla Perkjärvellä (nykyään asema Kirillovskaya). Hänen ensimmäinen vastaus seurakunnan neuvoston kirjalliseen ehdotukseen tulla kirkkoherraksi oli kielteinen. Isä Grigory neuvoi kuitenkin seurakuntalaisia lähtemään Isä Nikolain luokse ja keskustelemaan kasvotusten. Seurakunnan neuvosto valtuutti Aleksanterin ja Aleksandran Vasilievien pariskunnan sekä Boris Björklundin matkalle Viipuriin ja Perkjärvelle tavoitteena neuvottelut isä Svetlovskyn ja isä Shtshukinin kanssa. Heidän päämääränä oli suostutella isä Nikolai tulemaan Helsingforsiin seurakunnan vieraaksi. Useiden pyyntöjen jälkeen isä Nikolai hyväksyi seurakunnan kutsun ja suostui tulemaan Helsinkiin tutustuakseen seurakunnan asioihin paikan päällä. Tämä matka tapahtui heinäkuussa 1927. Helsingissä hän löysi seurakunnasta syvästi uskonnollisen yhteisön ja suostui tulemaan Pyhän Nikolauksen seurakunnan kirkkoherraksi.
Suomen hallitus (eduskunta) hyväksyi seurakunnan järjestysasiakirjan 23. joulukuuta 1926, jonka jälkeen järjestysasiakirjan kohdan 2. mukaisesti seurakunta oli velvollinen ilmoittamaan olemassaolostaan tiettyihin virastoihin sekä valitsemaan oman kirkkoneuvoston. Vasta tämän jälkeen seurakunta pystyi asettautumaan ortodoksisen piispan kanoniseen alaisuuteen. Yhteisön ensimmäiseksi piispaksi valittiin Länsi-Euroopan eksarkaattia johtanut korkeasti pyhitetty metropoliitta Jevlogi.
Pyhän Nikolauksen vastaperustettu seurakunta astui metropoliitta Jevlogin omoforin alaisuuteen ja asetti viralliseksi perustamispäivämääräksi 9/22. toukokuuta 1927, jona päivänä vietetään seurakunnan juhlapäivä.
Kirkkoneuvosto kokoontui silloin Vasilievien pariskunnan asunnolla. Siltä ajalta säilyi paljon mielenkiintoisiä Kirkkoneuvoston pöytäkirjoja. Esimerkiksi, kirkkoherra pyysi hankkimaan kynttilänjalan kymmenelle kynttilälle, astian pyhää vettä varten, aspergillumin, hienorakeisen sienen, proskuralautasen ja muita jumalanpalveluksen pieniä tarvikkeita. Vähitellen alkoi tulla kolehtilahjoituksia sekä kirkollisia esine- ja tarvikelahjoituksia. Seurakunta haki kirkolle paikkaa ja kääntyi varakkaiden henkilöiden puoleen saadaskeen omat kirkkotilat. Ensimmäinen jumalanpalvelus pidettiin kauppias Kovinin talolla Hakaniemessä syyskuussa 1927 Herran edelläkävijän ja Kastajan Johanneksen mestauspäivänä. Tämä paikka oli toiminut väliaikaisena temppelinä 11. maaliskuuta 1928 saakka, jolloin jouduttiin evakkoon isännän epäsuotuisan suhtautumisen vuoksi. Pian saattiin vuokrattua hirsitalo osoitteesta Kolmas linja 18. Talosta löytyi kaksi tai kolme huonetta pihan puolelta sekä iso sali toisen huoneen kanssa, jotka varustettiin temppeliksi.
Pyhän Nikolauksen kirkko oli toiminut Kolmannella linjalla kymmenen vuoden ajan. Vuonna 1938 aloitettiin nykyisen kivikirkon rakentaminen.
Vastarakennettu kirkko pyhitettiin käyttöön 11. joulukuuta 1938. Seurakunta alkoi kasvamaan vilkkaasti. Ensimmäisen kymmenen vuoden jälkeen Pyhän Nikolauksen seurakuntaan kuului yli 650 ihmistä.
Rovasti Nikolai Shtshukin oli suuri pastori, joka tulisella saarnallaan kutsui venäläisiä ihmisiä temppeliin, motivoi syntien katumukseen, innoitti, lohdutti ja rukoili puolesta. Ihmiset vastavuoroisesti rakastivat häntä ja tunsivat hänen vetovoimansa. Hänen hurskaan ajattelunsa ja väsymättömän energiansa ansiosta Helsingin seurakunnan pienestä innostuneiden henkilöiden joukosta kasvoi kokonainen seurakunta omineen kivikirkoineen, jumalanpalveluksineen ja seurakuntatoimineen. Hänelle oli ominaista harvinainen tahdikkuus ja hyvä organisaatiokyky.
Isä Grigory Svetlovsky muisteli kuolemansairaan isä Nikolain olleen täysin vihaton ja useasti pyytäneensä häneltä esirukousta omasta puolestaan. Isä Nikolain viimeiset sanat olivat: ”…jatkakaa esirukousta puolestani myöhemminkin!”. Hän kuoli Marian sairaalassa Helsingissä 21. joulukuuta 1940. Ensimmäisen panihidan yöllä rovasti Grigori Svetlovsky ilmoitti, että huomisesta lähtien hän tulee toimittamaan neljäkymmentä liturgiaa edesmenneen muistoksi. Useiden satojen seurakunnan jäsenten kyyneleiden saattamana hänet haudattiin seurakunnan hautausmaalla. Valitettavasti isä Nikolaille ei ehditty löytämään seuraajaa, minkä takia seurakunta jäi pitkäksi aikaa ilman kirkkoherraa. Etsintöjen jälkeen seurakunnalle löytyi kaksi vanhaa rovastia – isä Sergij Chetverikov ja isä Viktor Krohin, jotka vuorotellen toimittivat jumalanpalvelukset kirkossa. Tästä huolimatta kirkonherran toiminnot jäivät isä Grigory Svetlovskille. Hänestä tulikin kirkkoneuvoston puheenjohtaja.
Isä Sergij Chetverikov palveli Pyhän Nikolauksen kirkossa vain lyhyen ajan pakottavasta syystä. Vuonna 1939 hän lähti Valamoon, muttei enää pystynyt palamaan Länsi-Eurooppaan juuri alkaneen sodan takia. Silloin hän oli seitsemänkymmentä kolme vuotias. Vuoden 1940 jouluaattona isä Sergij veljeskunnan kanssa evakuoitiin Suomeen ja hän aluksi asui luostarin väliaikaisessa tilassa, jonka jälkeen hän muutti Helsingforsiin. Silloin hän palvelikin lyhyen ajan Pyhän Nikolauksen kirkossa ja myöhemmin muutti poikansa Feodisiy Sergeevichin luokse Bratislavaan. Isä Sergij kuoli 29. huhtikuuta 1947 Bratislavassa.
Seurakunta oli etsinyt pitkään uutta kirkkoherraa, joka olisi henkisesti isä Nikolai Shtshukinin vertainen. Isä Viktor Krohinin valinta kirkkoherraksi tapahtui vain viiden vuoden päästä joulukuussa 1945.
Kesällä 1945 tapahtui metropoliitta Evlogin johtaman Länsi-Euroopan eksarkaatin ja Venäjän Ortodoksisen Kirkon jälleenyhdistyminen, minkä ansiosta metropoliitta Evlogin seurakunnat, mm. meidänkin seurakuntamme, liittyivät Hänen Pyhyytensä Moskovan ja koko Venäjän Patriarkka Aleksiy I:n alaisuuteen. Todellisuudessa seurakunnan liittyminen tapahtui 8. lokakuuta 1945 Leningradin metropoliitta Grigoryn (Chukov) Helsingin vierailun aikana.
Tämä aikakausi merkitsi suurta hengellistä herätystä tuhansille ortodokseille Suomessa. Moskovan Patriarkaatti vastaanotti satoja vetoomuksia allekirjoituksineen eri puolilta Suomea, joissa pyydettiin järjestämään vanhan perinteen mukaisia jumalanpalveluksia. Näiden ihmisten sieluhoitotyö annettiin isä Petr Nortamolle. Isä Petr on myös haudattu seurakunnan hautausmaalle. Niinä vuosina Valamon luostarin veljeskunta päätti siirtyä Moskovan Patriarkaatin omoforin alaisuuteen. Pyhän Nikolauksen seurakunnan kirkko oli täynnä rukoilevia ihmisiä. Tämän takia syntyi tarve kirkon laajennukselle. Kirkon laajennusprojekti tapahtui arkitehtti I.N.Kudrjavzevin johdolla ja seurakunnan vahtimestarin I.V.Rosen aktiivisella osanotolla. Kirkon itäinen osa sai tilavan alttaritilan ponomaritiloineen.
Alttarin alla sijaitsevaan kryptaan valmistui uusi tila, jota nykyäänkin käytetään seurakunnan salina. Kirkko pyhitettiin 16. joulukuuta 1950.
Konevitsan Jumalanäidin ikoni tuotiin useasti Uudesta Valamosta kunnioittamista varten. Venäjän korkeasti pyhitetyt piispat vierailivat kirkossa. Valamon ja Konevitsan munkit useasti toimittivat jumalanpalveluksia Pyhän Nikolauksen kirkossa.
Seurakuntaa ovat johtaneet Venäjän Ortodoksisen Kirkon arvostetuimmat esipaimenet: metropoliitta Evlogi Georgievsky, metropoliitta Grigory Chukov, metropoliitta Nikolai Jarushevich, metropoliitta Nikodim Rotov, metropoliitta Filaret Vahromeev ja Hänen Pyhyytensä Aleksei II, Moskovan ja koko Venäjän patriarkka.
Yli 30 vuoden (pienellä välitauolla) seurakunta sai hengellista tukea nykyiseltä Hänen Pyhyytensä patriarkka Kirililtä. Hänkin kuuluu seurakunnan elävään historiaan.
Erityisesti ensimmäiset kymmenen vuotta omassa arkkipiispan työssä hän usein toimitti jumalanpalvelukset, saarnasi, tapasi seurakuntien kirkkoneuvostoja, tunsi seurakunnan jäsenistön ja oli ajan tasalla kaikkien tapahtumien suhteen.
6. toukokuuta 1974 Hänen Pyhyytensä patriarkka Pimen toimitti liturgian Pyhän Nikolauksen kirkossa. Patriarkka Pimen kävi toisen kerran Suomessa vuonna 1981 ajalla 31. elokuuta – 6. syyskuuta 1981.
21. syyskuuta 1994 Hänen Pyhyytensä Aleksiy II, Moskovan ja koko Venäjän patriarkka toimitti liturgian Pyhän Nikolauksen kirkossa. Ennen tätä hän useasti vieraili seurakunnissa ja toimitti jumalanpalvelukset johtavan arkkipiispan asemassa vuodesta 1986 lähtien ja siihen saakka kun hänet valittiin patriarkaksi.
Rovasti Viktor Krohin valittiin seurakunnan kirkkoherraksi vuonna 1945 (hänet oli haudattu seurakunnan hautausmaalla).
Hänen seuraajaksi valittiin isä Georgy Pavinsky, joka oli myös kronstatilainen pakolainen. Hän palveli seurakunnan kirkkoherrana 19 vuotta kuolemaansa saakka. Isä Georgy nukkui pois vuonna 1969 (hänet on myös haudattu seurakunnan hautausmaalla). Näillä pastoreilla oli korkea teologinen koulutustausta, koska he valmistuivat Pietarin Hengellisesta Akatemiasta vielä ennen vallankumousta. Molemmat suorittivat teologian lisensiaatin tutkinnot.
Vuonna 1969 seurakunnan yleisessä kokouksessa uudeksi kirkkoherraksi valittiin isä Nikolai Starostin, joka neljän vuoden päästä joutui anomaan vapautusta sairauden takia.
Vuonna 1973 seurakunnan yleisessä kokouksessa kirkkoherraksi valittiin isä Georgy Kilgast. Hänen kaudella Pyhän Nikolauksen seurakunta irtaantui Viipurin Pokrovan seurakunnasta ja seurakunnan nimi sekä järjestyssäännöt muutettiin.
Vuodesta 1985 lähtien kirkkoherrana toimi rovasti Mikhail Poljachenko. Vuodesta 1944 lähtien hän oli Pyhän Nikolauksen kirkon toiminnassa mukana: lauloi kirkkokuorossa, ylläpiti hautausmaata, useasti nousi kirkkoneuvoston jäseneksi sekä toimi seurakunnan taloudenhoitajana. Vuonna 1974 kirkkoneuvosto päätti, että hän tuli avustamaan isä Georgya diakonina. Mitropoliitta Nikodim vihki hänet diakoniksi ja vuonna 1980 Viipurin arkkipiispa Kiril vihki hänet papiksi. Vuodesta 1986 hän toimi myös Pokrovan seurakunnan kirkkoherrana.
1980-luvulla monet vanhat seurakunnan jäsenet siirtyivät toispuoleiseen maailmaan ja nuorisosta oli pulaa. Seurakunta hiljaisesti kuihtui ja heikkeni. Venäjän Ortodoksinen Kirkko kaikin tavoin osoitti huolenpitoa seurakunnan tilasta. Seurakunta sai kirkollista kirjallisuutta, kirkollista vaatetusta, astioita ja paljon muuta.
Neuvostoliiton hajoamisen jälkeen alkoi uusi maahanmuutto Suomeen. Seurakunta alkoi syntymään uudelleen. Seurakunnassa työskenteli papiston uusi sukupolvi. Hiljalleen kirkko täyttyi uskovaisista ihmisistä. Kirkkokuoro lauloi uudella voimalla. Jumalanpalveluksissa näkyi myös lapsia. Isä Mikhail Pojachenko kuoli vuonna 1998.
Kirkkoherrojen lisäksi seurakunnassa työskenteli joukko ahkeria pastoreita ja diakoneita: y.m. rovasti Sergij Chetverikov ja jumalanpalveluksissa avustanut munkkidiakoni Arseny Konev. Seurakunnassa myös palvelivat arkkidiakoni Mikhail Melnikov ja diakoni Feodor Lukjanov (haudattu seurakunnan hautausmaalla). Diakonina oli myös palvellut tuleva Pokrovan seurakunnan kirkkoherra rovasti Boris Pavinsky (haudattu seurakunnan hautausmaalla).
Isä Grigory Sandin (haudattu seurakunnan hautausmaalla) oli hurskas pastori ja tunsi läheisesti isä Johannes Kronstatilaisen, jolta sai siunauksen avioliitolleen. Ennen vallankumousta hän oli hyvin toimeentuleva ja harrasti hyväntekeväisyyttä avustamalla isä Johannes Kronstatilaisen perustamaa luostaria Pietarissa. Vallankumouksen seuraksena hän menetti kaiken omaisuutensa, muttei rikkoutunut henkisesti, päinvastoin vanhollisen Jobin tavoin hän vahvistui uskossa ja vahvisti muita.
Ainoastaan neljä mainutuista pastoreista ja kaksi kirkkoherraa, rovastit Viktor Krohin, Sergij Chetverikov, Georgy Pavinsky ja Boris Pavinsky, suorittivat virallisen teologian tutkinnon. Muut papit valittiin tavallisten hurskaiden seurakunnan jäsenten joukosta.
Seurakunnan kanttorin asemassa työskenteli pitkään kirkollinen säveltäjä Aleksey Ivanovich Krasnostovsky. Hän oli syntynyt Pietarissa 15. maaliskuuta 1880 reserviläisen sotilaan perheessä. Hän suoritti kanttorikursseja Hovin laulukappelissa. 17-vuotiaasta saakka hän toimi kappelimestarina. Hän valmistui Pietarin konservatoriosta säveltäjän ja kappelimestarin N.A.Rimski-Korsakovin luokalta. Vuodesta 1900 lähtien hän toimi kanttorina monissa Pietarin kirkoissa. Hän palveli kirkollisena kanttorina ja lauluopettajan Sinisen Ristin turvakodissa ja myöhemmin Pokrovan naisten seurakunnassa. Jonkin aikaa hän toimi kanttorina Orelin kaupungissa. Vuonna 1908 hänestä tuli Suomen Viipurin katedraalikirkon kanttori. Hän opetti laululuokkia myös koulussa. Vuosina 1938-1939 hänen sävellyksensä tuhoutuivat pommituksen aikana. Hän lähti evakkoon Sisä-Suomeen. Asui Migolin kylässä lähellä Tammerforsia (Tampere). Vuodesta 1950 hän asui lähellä Helsinkiä, sävelsi ja toimi kuolemansa saakka Pyhän Nikolauksen kirkon kanttorina.
Aleksey Ivanovich Krasnostovsky kuoli 8. helmikuuta 1965 (haudattu seurakunnan hautausmaalla).
Vuodesta 1979 seurakunnassa palvelee mitran käyttöön oikeutettu rovasti Orest Chervinsky, joka toimii samalla seurakunnan vahtimestarina. Kaikista edeltäjistä hänellä on pisin seurakunnan toimikausi.
Vuoden 2012 tammikuusta lähtien seurakunnassa toimii isä Vladislav Menshikov, joka oli toiminut seurakunnan diakonina vuodesta 2005.
Kanttori Taisija Voskoboinikova toimii seurakunnassa vuodesta 1989 lähtien.
Vuodesta 1989 lähtien seurakunnassa palvelee rovasti Nikolai Voskoboinikov, joka vuonna 1999 valittiin Pyhän Nikolauksen seurakunnan kirkkoherraksi.