Тобольский Кремль, окруженный белокаменными стенами, расположен на высокой террасе Алафейской горы, что возвышается над рекой Иртыш. В 16 веке здесь был построен первый деревянный острог, но уже в конце 17 века было принято решение о строительстве первого (и единственного в Сибири) белокаменного Кремля.
После крупного пожара 1677 года, в результате которого выгорела значительная часть Тобольска, из Сибирского приказа Москвы воеводе Петру Васильевичу Шереметеву пришло предписание: «впредь город Тобольск делать каменный и для того городского каменного строения велено отписать, где быть городу».
В 1683-1686 годах началось активное возведение каменных построек в Кремле артелями каменщиков Герасима Шарыпина и Гаврилы Тютина, присланными из Москвы и Великого Устюга. Вначале они начинают строить Софийский собор, а затем крепостные стены вокруг Софийского двора. Строительство стен и башен заняло около 10 лет.
Высота стен с 9 башнями достигала 4.5 метра, а их общая протяженность вокруг Софийского двора составила 620 метров. К югу от собора Алафеевская гора разрезана логом, который использовался для входа в Кремль со стороны Нижнего посада. Эту дорогу называли Прямской (или Софийский) взвоз. Над ними находилась проездная башня со Святыми воротами и надвратным храмом Сергия Радонежского, которые до наших дней не сохранились, так как позже на этом месте была построена Рентерея.
Основные белокаменные башни были построены уже в начале 18 века, когда строительными работами в Тобольском Кремле руководил Семен Ремезов. В 1782 году в Тобольске учреждается наместничество с подчинением ему городов Западной Сибири, которое потребовало строительства новых зданий. Губернским архитектором Гучевым, был разработан новый генеральный план города, а также проект перестройки старого Кремля. Классицизм требовал изменения замкнутой крепостной структуры Кремля.
При строительстве Дворца Наместника было решено разобрать часть крепостных стен, которые уже были не нужны для обороны города, так как владения России к тому времени простирались далеко в Сибирь, вплоть до Аляски. Значительная часть крепостных стен была разобрана в середине 19 века при строительстве комплекса зданий Тюремного замка.