Тюремный замок был построен в Кременчуге в 1805 году, находился он на Киевской улице (теперь Богдана Хмельницкого). Построен был по одному из первых в России типовых проектов тюрем для губернских городов архитектора А. Захарова, прославленного автора Адмиралтейства в Петербурге. Правда проект пришлось видоизменить, приспособив его к местным условиям. По административному статусу уездного города в Кременчуге необходимо было применить типовой проект для уездных городов. Но Кременчуг ни по количеству населения, ни по экономическому развитию не был похож на типичный уездный город.
К тому же местоположение города на границе трёх губерний привлекало значительное число преступного элемента. Поэтому типовой проект для уездного города оказался мал, а типовой проект для губернских городов использовать было нельзя, так как Кременчуг не был губернским городом. Вынуждено пошли на компромисс. Ограда и въездные ворота с башнями были выстроены по типовому губернскому проекту, а внутри двора построили не один корпус для заключённых, а целых три. В середине ХIX века эти одноэтажные корпуса разбираются и в центре двора сооружается двухэтажное безликое тюремное здание, просуществовавшее до II мировой войны. К сожалению фотографий тюрьмы нет.
Согласно Справочной книги за 1908 год Кременчуг
При тюремном замке существовала церковь построена в 1865 г.,
- престол во имя Божьей Матери «Всех Скорбящих Радости».
- Причт: св. Никол. Автоном. Роменский (Вес. у. д. Магденко),
- староста Ив. Ив. Богданов(Констант.-Зеленая, д. Сагала).