Изначальный храм этого посвящения был возведен в центре Павловской крепости при её строительстве, в 1777-1779 годах. Деревянная церковь была обнесена каменной оградой.

Новый крупный каменный храм взамен прежнего был освящён 29 июня 1853 года. Купола благолепного и большого храма были видны даже из соседнего города Георгиевска, а колокольный звон слышался за много верст, так как высота звонницы достигала 51 метра.

В 1937 году храм уничтожили. В годы советской власти здесь был кинотеатр "Россия".

В 1999 году на месте разрушенного храма по инициативе главы города Новопавловска В.Ф. Кузнецова совместно с храмом Владимирской иконы Божией Матери на средства прихожан и спонсорской помощи было начато восстановление церкви. На июнь 2011 года шли строительный работы по возведению нового храма.

Источник: http://drevo-info.ru/articles/17985.html

В 1853 г. в станице Новопавловской на средства прихожан и войсковых сумм был сооружен небольшой, рассчитанный на 500 человек, храм. Станица разрасталась, храм стал тесен.

В 1911 г. под влиянием настоятеля церкви, священника о. Иоакима Булгакова общество станицы Новопавловской приступило к постройке нового обширного каменного храма. Председателем строительного комитета стал священник о. И. Булгаков. Много было потрачено денег, много возникло трудностей, особенно после того, как подрядчик магометанин вовлек общество в судебный процесс. Но в итоге стройка успешно закончена.

24 ноября 1916 г. храм был торжественно освящен епископом Фаддеем (Успенским) при многочисленном стечении народа из окрестных станиц: Старопавловской, Марьинской, Солдатской, Зольской. После освящения была божественная литургия, проведенная епископом Фаддеем в сослужении нескольких иереев и диаконов при пении двух хоров певчих: монашествующих Георгиевского женского монастыря, что на реке Куре, и местного под управлением священника деревни Орловки, А. Попова. Каждый взирающий на храм поражался его обширным размерам, изяществом работы и выдержанному русскому стилю.

Общество станицы Новопавловской по инициативе и под руководством священника о. Булгакова также построило здание церковно-приходской школы, двухэтажное каменное здание министерского училища и деревянную церковь в деревне Орловке, прежде приписной к новопавловской церкви.

Источник: Владикавказские епархиальные ведомости 1916 г. № 24 с. 1013-1015.