The church was built on the site of the Saray Mosque, which was destroyed in 1882, after the liberation of Bulgaria by Russia from the Ottoman Empire.
It was built as the official church of the Russian Embassy, which was located next door, and of the Russian community in Sofia, and was named, as was the tradition for diplomatic churches, for the patron saint of the Emperor who ruled Russia at the time, Nicholas II of Russia.
The church remained open after the Russian Revolution and during the Communist period in Bulgaria (1944–1989), though priests and church-goers were carefully watched by the State Security police.
The crypt housing the remains of Saint Archbishop Seraphim is located beneath the Russian Church's main floor.
Dozens of people still visit the grave of the archbishop, who died in 1950, praying and leaving notes asking for wishes to be granted.