В старом Оренбурге примерно в 1812–1814 годах к западу от крепости с маленького поселения ссыльных начала застраиваться Голубиная слободка. Селили сюда преимущественно отставных солдат, мастеровых и «других состояний» людей, но не казаков. В 1819 году в слободку из города выселили беднейшие слои, и она значительно выросла. Церкви же своей в слободке не было, и жители её по любой непогоде ходили на службы в крепость. После страшной эпидемии холеры в 1848 году, почетный гражданин, купец первой гильдии, Михаил Стефанович Деев, обратился к военному губернатору В.А. Обручеву с просьбой разрешить построить в слободке каменную церковь как благодарность Богу от избавления от страшного мора его семьи. Для строительства храма городская дума безвозмездно передала М.С.Дееву небольшой участок.
Храм был заложен 30 апреля 1852 года благочинным Василием Ольшанским, а 30 октября 1853 года строительство было завершено. Освящена церковь 22 ноября 1853 года преосвященнейшим Антонием, епископом Оренбургским и Уфимским.
В клировой ведомости за 1853 год дается следующее описание: «Здание каменное с таковою же колокольнею, новая, покрытая железом и кресты медные, золоченые через огонь. Престол в ней один в именование Покрова Пресвятой Богородицы. Утварью снабжена достаточно. Причта положено: один священник, диакон, дьячок и пономарь. Земля церкви, отведенная в узаконенной пропорции, с погостом – вечное владение. Священники и церковнослужители никакою землею не пользуются. Домов собственных священнослужители не имеют. На содержание священно- церковнослужители ни откуда ничего не получают, а пользуются только братскими доходами. Зданий при церкви никаких нет. Расстоянием сия церковь от Духовной Консистории в 353 верст. Духовное правление и местный благочинный в самом городе. Опись церковному имуществу составлена по вновь изданной форме. Приходно-расходные книги о суммах свечной и кошельковой за шнуром и печатью Оренбургского духовного управления и скреплены подписью оренбургского протоирея Розанова, выданные в 1853 году. Копия метрических книг начата с ноября 1853 года. Исповедных росписей нет. Обыскной книги тоже пока нет».
Сыновья купца Деева, Стефан и Николай, в 1855 году, когда их отец заболел, решают построить два придела к Покровской церкви во имя Архангела Михаила и Сергия Радонежского. В 1857 году приделы достроены и освящены, но Михаил Стефанович до этого уже не дожил. Церковь огородили оградно – черной решеткой. Храм стоит на пригорке, возвышаясь на жилищами человеческими как белый маяк или корабль.
При церкви содержалось несколько школ и училищ, жертвовались средства на лечение бедным и содержание семей умерших священнослужителей.
В 1933 по решению городского совета храм Покрова Пресвятой Богородицы был передан Оренбургскому Облпотребсоюзу и переделан в цеха: столярный, мебельный, бондарный, сушилку леса. В 1991 году началось постепенное возрождение храма: прихожане начали приводить в порядок здание, пока еще в нем работал бондарный цех, а на паперти ремонтировали телевизоры и холодильники. В 2008 году при храме начались занятия для студентов Оренбургской Духовной семинарии.
Главные святыни храма:
- Иконы из Казанского кафедрального собора, взорванного в 30-е годы кисти известных братьев художников В.Е. и К.Е. Маковских. Иконы были безвозмездно переданы храму в 1993 году из запасников Музея изобразительных искусств директором Дубининой Натальей Ивановной.
- Список чтимой в Оренбургском крае Табынской иконы Божией Матери, сохраненный православными христианами в годы лихолетья. Эта икона долго сохранялась в одном из сел Оренбуржья в сельском доме за печью и долгое время была утешением в тайной молитве жителей села.
- Почитаемая прихожанами храма икона Божией Матери «Скоропослушница».
- Почитаемая прихожанами храма икона Божией Матери «Всецарица»
- Почитаемая прихожанами храма «Блаженная Ксения»