After the commissioning of Samara-Zlatoust railway the northern border of Ufa was populated by the railway workers and their families. The seemingly unapproachable mountains were sprinkled with buildings. Railway workers and their families filled the parish of a new church which was constructed to commemorate the engagement of the last imperial couple in 1890. On March 22, 1897 the temporary church at the railway station was consecrated and named after Nicholas the Wonderworker and the Sanctifier. On November 28, 1897 they consecrated the aisle of the Ascension. Archpriest Sokolov was appointed the first senior priest of the church, whereas Dublinsky was appointed churchwarden. The church was located in one of the busiest sites of the city. Its parish amounted to 402 persons.
Later the temporary church was substituted with a stone one. Its foundation stone was laid on May 23, 1899. St. Nicholas Church was constructed in accordance with the typical project which was later used for the Church of the Nativity of the Blessed Virgin. At the same time the two churches looked very different. The new church was five-domed with a stone bell tower. The largest of its six bells was 115 poods (1,884 kg) whereas the smallest one weighted 34 poods and 5/8 pounds (almost 600 kg). The church was heated with six stoves. It also had a gate-house and a wooden house for the clergy.
In 1903 upon the decree of Emperor Nikolas II senior priest Sokolov was awarded the order of Saint Vladimir. Kedrov was the next senior priest after Sokolov. Since January 1, 1915 until its closure the church was headed by Vasily Lezenkov.
Before the World War I the road from the railway station passed the St. Nicholas Church along the Shosseynaya (Dzerzhinsky) Street. That is why in 1891 they built the so-called Tsar Gates on Shosseynaya Street to meet the crown prince of the Russian Empire Nikolas who was coming back from Japan. That year, though he decided to choose a southern route. When on June 28, 1904 he finally came to Ufa he was already Emperor Nikolas II. The tsar was greeted by the prominent citizens, priests, and merchants. There are no official documents about the event. But they said that the tsar was expected to show up in St. Nicholas Church which was built in honor of his patron saint and his engagement. An extraordinary event disrupted these plans. This is what Aleksandr Sokolov-Novosyolov wrote in his book Armed Underground Resistance: "… a red-headed officer with a blue shoulder band is going down the stairs. Beautiful and majestic ladies are coming to the tsar with a dish of bread and salt of hospitality. Behind the ladies follow the governor and a bunch of city officials. This moment the entrance roof overhang cracked and collapsed on the railway platform not far from the officials. Everyone shrank aside. Somebody cried "Bomb!" The tsar also ran away". Naturally, there is a great deal of fiction in this book rather than the truth since it's a book about the revolutionaries. Nevertheless, they did not see the Emperor in the church.
Ufa merchant Ivan Luzin was elected the churchwarden of St. Nikolas Church several times. Worker Osip Melnikov was the last churchwarden. The church was the first one to close in the city in 1924. The building was given to the department of railway workers' trade union. The property was given to St. Symeon Church and the warehouse of the city utility service. The same year they started reconstructing the initial building. In the 1950s the building underwent the most substantial reconstruction.
Until recently the building has been occupied by the Andreev railway club and Ufa branch of Samara railway institute. Later the church was given back to the parish.