Тюремний замок був побудований в Кременчуці в 1805 році, знаходився він на Київській вулиці (тепер Богдана Хмельницького). Побудований був по одному з перших в Росії типових проектів в’язниць для губернських міст архітектора А. Захарова, прославленого автора Адміралтейства в Петербурзі. Правда проект довелося видозмінити, пристосувавши його до місцевих умов. За адміністративним статусом повітового міста в Кременчуці необхідно було застосувати типовий проект для повітових міст. Але Кременчук ні за кількістю населення, ні з економічного розвитку не був схожий на типовий повітове місто.
До того ж розташування міста на кордоні трьох губерній приваблювало значне число злочинних елементів. Тому типовий проект для повітового міста виявився малий, а типовий проект для губернських міст використовувати не можна, так як Кременчук не був губернським містом. Змушене пішли на компроміс. Огорожа та в’їзні ворота з вежами було побудовано за типовим губернському проекту, а всередині двору побудували не один корпус для ув’язнених, а цілих три. В середині ХIX століття ці одноповерхові корпуси розбираються і в центрі двору споруджується двоповерхова безлике тюремне будівля, яка проіснувала до II світової війни. На жаль фотографій в’язниці немає.
Згідно Довідкової книги за 1908 рік Кременчук
При тюремному замку існувала церква побудована в 1865 р,
престол в ім’я Божої Матері “Всіх скорботних Радості”.
Причт: св. Микол. Автоном. Роменський (Вага. У. Д. Магденко),
староста Ів. Ів. Богданов (Констант.-Зелена, д. Сагана).