Церковь была построена по образцовому проекту военных храмов, утверждённому Строительной комиссией в 1901 г. (арх. Ф.М. Вержбицкий). Всего в Российской Империи к 1917 г. было выстроено не менее 69 таких церквей.
Данный храм для расквартированного в Павлограде 135-го пехотного Керчь-Еникольского полка был освящён в1907 г. во имя вмч. Георгия Победоносца.
С 25.09.1900 г. полковым священником являлся Иоанн Иоаннович Росляков (1863-…). Полковая церковь находилась на Военной ул. рядом с казармами.
В 1924 г. церковь была закрыта и обезглавлена. Впоследствии с её восточной стороны были сделаны пристройки, а над западным фасадом возведён новый фронтон.. В разные годы в здании располагался клуб и спортзал в/ч А-0626.
С 1992 г. с разрешения командования в/ч в храме был совершён первый молебен, а в 1995 г. здание бывшей полковой церкви было передано УПЦ в безвозмездное пользование. С 2001 г. после официальной регистрации прихода в храме стали совершаться регулярные Богослужения. В это же время в/ч (бывший учебный полк связи РВСН), на территории которой находилась церковь, была ликвидирована.
В 2010-2011 годах в храме были проведены реставрационные работы, носившие в основном косметический характер. Исторический облик храма ввиду затратности было решено не восстанавливать.
29.08.2011 г. над западным фасадом была установлена лишь небольшая золочёная главка со крестом, а 22.09.2011 г. митрополит Днепропетровский и Павлоградский Ириней (Середний) совершил чин полного освящения храма с новым посвящением престола во имя Покрова Превятой Богородицы.
В настоящее время храм находится в юрисдикции УПЦ (Московской Патриархии).
Источники: РГИА ф. 806, оп. 8, д. 263 (1907 г.); Цитовичъ Г.А. Храмы Армiи и Флота, 1913, сс. 377-378
