Царское правительство, присвоением Сибири, понимало какую обширную и суровую тюрьму оно получило и всячески старалось заселить этот безлюдный край. Этапные и каторжные тюрьмы существовали практически во все времена истории Тобольска. Сначала это были неприспособленные для этих целей помещения, но во второй половине XVIII в. в районе Курдюмовского оврага был заложен деревянный острог для содержания преступников и арестантов.
В конце XVIII в. острог был расширен — в нем построили кирпичные корпуса, существовавшие наряду с деревянными. Но он не мог вместить всех отправляемых преступников в Сибирь, поэтому требовались новые здания. В конце XVIII в. в Западной Сибири было выстроено 5 острогов и два работных дома — в Тобольске и Томске. Остроги были небольшими и могли вместить до 30 человек, а все остроги Западной Сибири — около 150 человек.
Дальнейшая колонизация Сибири в начале XIX в. и рост количества ссыльных заставляет правительство принимать решения по строительству новых острогов — «тюремных замков», или типовых тюрем. К 1819 г. в Западной Сибири было уже 14 острогов и три острога в Восточной Сибири.
В остроге находилось особое помещение гауптвахты, где размещался палач. Палачи, как правило, выбирались из среды арестантов. Это были опасные преступники, сумевшие заслужить доверие властей и получавшие ежегодное жалование за свою работу.
Особенностью Тобольского острога были «секретные нумера», в которых содержались, прикованные к стене на цепи, особо опасные преступники. Одним из известных преступников был некто Иван Коренев, совершивший, по его словам, 18 убийств. В Тобольске Коренев приобрел большую известность. Арестанты его уважали, чиновники боялись и воображали его диким зверем, напротив, их скучающие жены принимали Коренева за чародея и ходили к нему за советом. Когда в 1850 г. в острог прибыли осужденные петрашевцы, Коренев, к всеобщему удивлению, отнесся к ним с пониманием, даже обучил некоторым тюремным премудростям.
Содержались в «тюремном замке» известный фальшивомонетчик, мастер глиняных миниатюр Игнатий Цезик и изготовитель фальшивых документов Петр Ветвеницкий.
После постройки в Тобольске новой тюрьмы в 1855 г. старый острог был реконструирован и постепенно обновлен. В 1913 г. в составе комплекса значились арестантский корпус, казармы, конторы, женские камеры и административные корпуса. В 1930-х гг. тюрьма была перестроена и расширена. В советское время комплекс старого острога использовался по своему назначению.
В настоящее время здесь размещается женская исправительная колония.