В 1999 году жители посёлка обратились к архиепископу Ростовскому Пантелеимону (Долганову) за благословением на проведение учредительного приходского собрания. В том же году благочинным Матвеево-Курганского округа протоиереем Николаем Чернявским собрание было проведено, и образовался приход. Небесным покровителем новой общины был избран прославленный в том году блаженный Павел Таганрогский. Службы проходили в здании заброшенного летнего кинотеатра, переданного поселковой администрацией для нужд прихода и переоборудованного под молитвенный дом.
В 2000 году архиепископ Пантелеимон, идя навстречу просьбе ветеранов Великой Отечественной войны Матвеево-Курганского района, благословил именовать будущую приходскую церковь храмом в память Победы на Миус-фронте в годы Великой Отечественной войны, в воспоминание о более чем 800 тысячах воинов, погибших на Южном фронте.
В 2003 году для консолидации усилий в деле строительства храма и для придания большего значения строящемуся храму, ветеранские организации Матвеево-Курганского, Куйбышевского и Неклиновского районов, а также казаки Матвеево-Курганского юрта провели объединительное собрание, согласно которому была образована инициативная группа по строительству храма-памятника. В том же году был разработан и утверждён проект церкви, пройдена Государственная вневедомственная экспертиза и начато строительство.
1 мая 2015 года на храм были водружены центральный купол и крест. 14 февраля 2016 года митрополит Ростовский Меркурий совершил чин великого освящения церкви - она стала первой в России приходским храмом, освященным во имя праведного Павла Таганрогского.
http://mk-blago.ru/prikhody/m-kurgan%202.htm