The Tobolsk Kremlin encircled by white stone walls is located on the high bench of the Alafeyevskaya Gora dominating the Irtysh river. The first wooden stockade was built there in 16 century. And already in 17 century it was decided to erect the first (and a single one in Siberia) white stone Kremlin.

After a big fire of 1677 the Siberian prikaz sent to voivode Pyotr Vasilyevich Sheremetyev an order to erect only stone buildings in Tobolsk. As a result of the fire most of Tobolsk was burnt.

Stone buildings were actively erected in the Tobolsk Kremlin during 1683-1686. The construction was carried out by the mason artels of Gerasim Sharypin and Gavrila Tyutin sent from Moscow and Veliky Ustyug. At first they began to erect the Cathedral of St. Sophia and then the walls surrounding the Sophia Court. It took 10 years to build the walls and towers.

The walls featuring 9 towers reached the height of 4.5 meters stretching around the Sophia Court for about 620 meters. To the south from the Cathedral of St. Sophia the Alafeyevskaya Gora was cut by a ravine used as an entrance to the Kremlin on the side of the Nizhny Posad. The road was called Pryamskoy (or Sophia) vzvoz (an uphill road). On the road there were also the Holy Gate with the Gate Church of St. Sergius of Radonezh but they didn’t survive to our days.

The main white stone towers were built already at the beginning of 18 century when the construction works in the Tobolsk Kremlin were guided by Semen Remezov. In the Tobolsk Kremlin new stone buildings appeared after 1782 when the city was made the administrative center of Tobolsk vice-regency. An architect Guchev developed the new general urban plan and the Kremlin reconstruction project. Classicism required changing the closed fortress structure of the Kremlin.

So, during the construction of the palace of the vice-regent it was decided to pull down some of the walls, which were already unnecessary to defend the city, as by that time the territory of Russia stretched far beyond Siberia. Most of the walls were dismantled in the middle of 19 century during the construction of the Tobolsk prison castle.