Первые упоминания о городской тюрьме (остроге) как о непременном атрибуте города встречаются уже в первых документах о шуйской крепости 16-17 вв. Тюрьма неоднократно разрушалась (при разорении Шуи поляками, пожарах), возобновлялась, перестраивалась, о чем сохранились документы (акты В. Борисова 17 в. о перестройке тюрьмы, содержащая смету, перечень строительных материалов). Узниками шуйской тюрьмы в разное время были известные в российской истории личности – от бояр времен Иоанна Грозного и Бориса Годунова до революционера и героя гражданской войны М.В. Фрунзе.
Деревянная тюрьма в кремле-осыпи была обнесена тыном. Тюрьма располагалась на месте соляных амбаров. После пожара 1792 г. тюрьма временно переносилась в богадельню при Троицкой церкви (городское кладбище). Каменная церковь при тюрьме сооружена на средства “доброхотных дателей, благодаря стараниям шуйского купца И.С. Гундобина”. Освящена 08.10.1872 г. В 1887 г. при церкви построена каменная колокольня вместо деревянной. На колокольне было 5 колоколов, вес большого составлял 52 пуда, всех – 146 пуд (1898 г). Храм теплый, одноглавый. Вход был с юго-запада. Хоры храма соединялись крытой галереей с тюремным двором (с северной стороны). Существует версия о преемственности названия церковного престола тюремного храма от древней церкви, существовавшей в шуйском кремле.
Согласно шуйскому историку В. Борисову, Никольская деревянная надвратная церковь сожжена поляками в 1609 г. Напротив Никольской церкви - в старом Покровском соборе до революции хранилась местночтимая икона Иоанна Воина, хранившаяся сначала в шуйской тюрьме, затем в здании городского суда. Иконе молились об открытии воров. На иконе была надпись “Иоанна Воинственника Шуйской воеводской канцелярии воеводы Ильи Андреева сына Обухова 1747 г.” Сейчас здание церкви перестроено, используется в хозяйственных целях, колокольня не сохранилась.