Церковь располагалась на Московском проспекте в тюремном замке, ограда которого имела вид крепостной стены с башнями по краям. До 1879 года в тюрьме не было храма и религиозные потребности заключенных православного вероисповедания удовлетворялись причтом Иосифо-Георгиевской Церкви. Духовник заключенных, священник Госпитальной церкви при помощи сочувствовавших лиц получил разрешение устроить храм на территории тюрьмы.
22 декабря 1879 года храм был освещен преосвященным Александром во имя Покрова Богородицы. Богослужения в храме совершались по воскресным и праздничным дням. Храм разместился во втором здании тюрьмы, в самом дальнем корпусе, в трёх рядом расположенных камер, которые были соединены между собой. Под алтарь была приспособлена самая маленькая камера, обращенная на север. В центральной молились прихожане, живущие недалеко от тюрьмы и включенные в её приход. В самой дальней комнате молились православные арестанты. Арка с решетчатыми железными дверцами отделяла городских прихожан от арестантов. Церковь освещалась пятью окнами и отапливалась железной печью. Иконостас был одноярусный, окрашенный белой краской с иконами работы ташкентского художника Девеля.
Чтобы попасть в церковь, прихожанам с города необходимо было проходить от ворот через всю территорию тюрьмы, далее из общего корпуса в церковь вели две двери — одна в вольное, а другая в арестантское отделение.
В 1886 году было принято решение перенести церковь на край тюремной ограды, отложили из-за нехватки средств. В 1898 году, усердием члена Сырдарьинского попечительного комитета П.А. Собенникова храм был заново отремонтирован. Иконостас окрасили красной масляной краской и украсили золотым багетом; царские врата золоченые резные; алтарь оклеен голубыми, а стены храма белыми обоями. Колокольней служили 2 деревянных столба с перекладиной, с одним колоколом весом в 7 пудов 30 фунтов.
С 1881 года Александр Григорьевич Вергелесов служил священником в Покровском храме. С 16 декабря 1886 года священником был Иоанн Андреевич Марков.
В 1905 году по проекту артиллерийского офицера Н.И. Габбина начато строительство нового храма во имя Святых Апостолов Петра и Павла при ташкентской тюрьме. 17 декабря 1906 года была освящена новая тюремная церковь во имя апостолов Петра и Павла (на 300 прихожан и 150 заключенных). Тюремная церковь была построена в псевдорусских формах и имела вход с Московской улицы. Коммерции советник Н.И.Иванов для церкви пожертвовал иконостас, заказанный в Москве.
В 1898-1903 годах священник тюремной города Ташкента Церкви был Александр Червяков. В 1910 и 1911 годах священник Ташкентской Петро-Павловской тюремной церкви К. Боголюбов.
После революции купола сняли. В 1941 году на месте тюремного замка разместили эвакуированный из Москвы завод парашютно-десантного имущества, а в здании церкви сделали киноклуб, который простоял до середины 50-х годов. Здание церкви было без колокольни, купола и без башенок на крыше. Позже сделали клуб, который сдавали для школьных вечеров и других мероприятий. Во второй половине 1960-х гг. построили швейную фабрику «Юлдуз», здание церкви было снесено.
Книги: К истории христианства в Средней Азии. По стопам Апостола Фомы. Туркестанская Епархия в документах и комментариях 1867-1918.
