The wooden Church of the Savior was built back in 1587 after the construction of the first prison and the construction of the Trinity Church. In 1593, the exiled Uglich bell was raised to the bell tower of this church, which alarmed people about the murder of the infant Tsarevich Dmitry.
At the end of the XVII century the wooden Church of the Savior burned down, was restored, but existed in a new form for a very short time.
In 1709, under Metropolitan Philotheus (Leshchinsky), in honor of the victory near Poltava, a new stone church was laid next to the wooden one. It was erected by the "care" of the merchant Stefan Tretyakov in four years. In 1772 and 1791, two side chapels appeared at the temple — the north and south. The bell tower was built only in the second half of the XIX century.
In the church there was an image of the "Uncreated Saviour". This icon was sent to Tobolsk during the reign of Tsar Fyodor Ioannovich, to the Trinity Church. Of the precious items of the Church of the Savior, silver wedding crowns with white topazes, weighing 2 pounds 2 spool, should also be noted. They bore the inscription: "The city of Tobolsk Trinity Cathedral".
There was a parish cemetery attached to the church.
In 1844, the funeral service of the Decembrist Baryatinsky, who had been exiled in Tobolsk since 1839, was held in the church.
Alexander Petrovich Baryatinsky was a representative of the richest family of princes, a participant in the Patriotic War of 1812, adjutant to the commander-in-chief of the 2nd Russian Army. Baryatinsky did not take direct part in the uprising on Senate Square, but was arrested as a member of the "Southern Society" and sentenced to hard labor forever.
On August 20, 1884, a memorial service was held in the church in memory of the Decembrist Alexander Petrovich Baryatinsky.
In the second half of the XIX — early XX century The Spasskaya Church was assigned to the Theotokos-Vvedenskaya (Nikolskaya) church, although it had its own parish.
At the end of the XIX century a priest and a psalmist were listed on the staff of the church. Since 1885, the priest Nikolai Nikolaevich Unzhakov has always served in the church, only the psalmists have changed. For example, in 1895, Deacon Dmitry Yakovlevich Ivanov (27 years old) served as a psalmist.
On October 12, 1911, a funeral service was held in the Spasskaya Church for the local historian Yevgeny Vasilyevich Kuznetsov, who died on October 10 at 5 p.m. in the Slauta house on Spasskaya Street.
After the revolution of 1917, the church was closed. In the 1930s, the church was decapitated. During the Soviet years, there was a registry office in the church. Later it housed art workshops. On October 7, 1975, a treasure of paper banknotes of 1898−1921 was found in the masonry of the wall of the Church of the Savior. It is currently under restoration.