Previously, the wooden Trinity Church of the Kabardian Regiment was situated between  Kadetskaya Line and Tuchkov Lane. Later the Astrakhan Dragoon and Keksholm regiments were located here. For them the Nikolsky Church was constructed, also a wooden one, on the site of the Trinity Church.  Soldiers and officers particularly revered the icon of Saint Catherine in this church. People often  called the church by that name: Catherine's church. 

In 1773 the church was consecrated again in honor of Saint Catherine. It  was granted to the Keksholm Regiment.

In 1809 the Church of Saint Catherine the Great Martyr burned down. All the church belongings were lost but the icon of Saint Catherine was saved. Religious believers started donating money for a new church.

In 1811 the architect Andrei Alekseevich Mikhailov II created a project of a stone church.  The temple was consecrated on   2 November  1823. This building was the most noticeable work by the architect Mikhailov II. It stands out among other buildings of Vasilievsky Island, the dome of the church can be seen from far away. The Church of Saint Catherine the Great Martyr played an important role in the life of Vasilievsky island. The main parishioners  of the Church of Saint Catherine the Great Martyr were workers of the stock exchange and the port located nearby on the Makarov embankment at the spit of Vasilievsky Island. It was visited by merchants, salesmen, scientists, artists, officials, men of arms, artisans.

Prior - pastor Anton Tikhomirov