Padre Nikolaj nasce a San Pietroburgo il 20 febbraio 1867, da famiglia nobile. Si diploma all’Accademia militare per i cadetti nobili. Nel 1893 termina gli studi all’Accademia teologica ortodossa di Mosca e nel 1890 è ordinato sacerdote ortodosso. Già durante gli studi tiene contatti con i domenicani di Roma e con i gesuiti di Parigi. Nel novembre 1894 a Roma passa ufficialmente alla Chiesa cattolica. A Roma è ricevuto dal Papa Leone XIII; in seguito si sposta a Parigi e vive presso i padri assunzionisti. Nel 1897 si incontra a Leopoli con padre Andrej Šeptickij, igumeno del monastero di Sant’Onofrio, futuro metropolita dei greco-cattolici della Galizia. Nel 1905, dopo la promulgazione del manifesto imperiale sulla libertà di professione religiosa, ritorna in Russia. Inizialmente esercita il ministero nelle parrocchie di Mosca e dal 1907 a Kiev e a Odessa. Dal 1908 è redattore della rivista «Vita ecclesiastica e sociale». In questo periodo opera attivamente per consolidare la chiesa greco-cattolica in Russia. Dal 1919 vive a Bobrov, regione di Voronež. Nel 1920 ritorna a Kiev dove celebra nella chiesa greco-cattolica del Sacro Cuore di Gesù. Dal 1924 vive a Odessa; nel 1925 ritorna a Kiev. Nel 1928 si sposa per la seconda volta e quindi rinuncia allo stato sacerdotale.
Il 14 novembre 1937 è arrestato con l’accusa di «attività spionistica a favore di un paese straniero». Il 25 gennaio 1938 è condannato alla pena capitale e il 4 febbraio 1938 Nikolaj Tolstoj viene fucilato nella prigione di Kiev.