Здание станичного уездного правления в Павлодаре, являющееся архитектурным памятником, расположено в историческом центре города и занесено в реестр памятников культуры местного значения. Построенное после крупного пожара 1901 года, здание заменило выгоревшие деревянные постройки на кирпичные. Его использовали до 1920 года, а в подвале находился карцер для особых правонарушителей.
До революции в Павлодаре действовало станичное уездное правление, состоявшее из атамана, его помощника, судей и казначея. Эти лица отвечали за порядок в станице, следили за имуществом населения и занимались ремонтом инфраструктуры. Наказания за проступки варьировались от штрафов до ареста и телесных наказаний, о чем рассказывает краевед Людмила Баюшева.
Во время революции 1918 года белогвардейцы использовали карцер для заключения большевиков и революционеров. После революции в 1919 году в здании открыли пункт радиосвязи и телефонную станцию, которые функционировали 10 лет. Позже здесь располагались различные госведомства, и на данный момент здание продолжает использоваться государственными органами.
Существует также легенда о том, что в подвале дома купца Дерова, где с 1920 года разместились органы госбезопасности, проходили пытки осуждённых. Сообщается, что подземный проход вел непосредственно к реке Иртыш, через который утилизировали тела расстрелянных. На пересечении улиц Астана и Лермонтова в настоящее время расположено современное здание, однако на этом месте ранее находилась «Белая» тюрьма, построенная в 1880 году.
В этой тюрьме отбывали наказания как уголовные преступники, так и политзаключённые, включая известных личностей, таких как лидер движения «Алаш» Алихан Бокейханов и писатель Александр Солженицын. Из-за высоких заборов вокруг тюрьмы также ходили слухи о совершенных там преступлениях.
