До начала XX века Стефанидинодар не имел своего храма – жители деревни вынуждены были ходить на службы в Свято-Вознесенскою церковь села Круглое.
Решение крестьян о строительстве собственной церкви было утверждено 26 мая 1894 года на сходе сельского общества. Новые землевладельцы постановили отвести 33 десятины полевой земли и усадебные места для довольства причта. Строительство церкви было завершено в 1896 году «по усердию и на средства прихожан».
Деревянная церковь с обыкновенными колоколами последней формы была построена по плану, выданному Екатеринославской духовной консисторией. Пятиглавый храм с колокольней возвели на кирпичном фундаменте, обшив его снаружи тёсом и покрасив масляной краской снаружи и внутри. Железные крыши храма были окрашены в зеленый цвет. Внутреннюю роспись выполнил в 1899 году маляр Казаков, проживавший в посаде Азов.
Длина церкви вместе с колокольней составляла 14 саженей, наибольшая ширина 8,3 и высота до верха карниза 3,3 сажени. Колокольня в три яруса, общей высотой до верха карниза 7 саженей. Церковь имела три наружных двухстворчатых двери, обшитых железом, и одну одностворчатую, а также 18 больших окон и 8 малых (на средней главе). Во внутреннем пространстве церкви были иконостас размером 12,5 аршина в длину и 9 в высоту. Здание церкви не отапливалось. При церкви имелась крытая железом глинобитная сторожка длиной 12, шириной 9 и высотой 4 аршина. Она была построена в 1896 году, имела 8 окон и 4 двери. Ближайшая к церкви чужая постройка (жилой дом священника) находилась с западной стороны, на расстоянии 50 саженей.
Из-за бюрократических проволочек, связанных с оформлением отвода полевой земли и усадебных мест для причта, между окончанием строительства храма и открытием в нём прихода прошло более четырех лет.
9 ноября 1899 года храм был освящён во имя Рождества Пресвятой Богородицы, а в 1900 году был утвержден его староста. Им стал стефанидинодарский крестьянин Иван Григорьевич Буцан. Затем, по указу Святейшего Синода от 26 февраля 1901 года, был открыт и самостоятельный приход Рождество-Богородичной церкви.
Первым настоятелем храма стал Константин Иванович Духовской. В августе 1902 года его назначили священником церкви с казенным жалованьем 294 рубля в год. 30 ноября того же года Духовской был утвержден законоучителем Гостомиловского народного училища – вместо Гавриила Алексеева – священника села Круглого, пребывавшего в этой должности с 15 декабря 1901 года. 1 октября 1903 года заполнилось и вакантное псаломщицкое место, на которое был определен заштатный псаломщик Михаил Аристархович Биантовский. Он прослужил в Рождество-Богородичной церкви пять лет – 27 октября 1908 года его перевели в Варваринскую церковь села Карнауховки.
Церковно-приходское попечительство храма было утверждено в апреле 1903 года. В его состав входило 17 человек.
Новым псаломщиком стефанидинодарской церкви стал Григорий Феодорович Артеменко – выпускник второклассной школы, работавший учителем с 1905 по 1909 год. Он довольствовался казенным жалованьем, составлявшим 98 рублей в год. Просфорней церкви значилась Дарья Левицкая.
Первый храм прослужил стефанидинодарцам около четверти века – в 1920-х годах он загорелся от удара молнии во время ночной грозы и огонь уничтожил церковь дотла. Однако усердием и стараниями прихожан на месте сгоревшей церкви была построена новая. Но и её время оказалось недолгим. В 1934 году было принято решение о закрытии этого храма, и постановлением Стефанидинодарского сельского совета от 2 октября 1938 года община верующих была ликвидирована. После прекращения религиозной деятельности здание церкви пустовало. Во время войны его разобрали, использовав материалы для строительства оборонительных сооружений.
Вместо утраченной церкви в Стефанидинодаре с 1942 года действовал молитвенный дом. Его настоятелями являлись священник Трояновский Тихон Дмитриевич (с. 20.10.1943г. по 12.06.1952г.); иеромонах Антоний – Рогулин Алексей Григорьевич (с 17.06.1952г. по 02.09.1953г.); священник Парфененков Федор Данилович (с 07.09.1953г. по 16.02.1958г.); священник Прокопенко Стефан Григорьевич (с 29.04.1958г. по 08.06.1958г.) и священник Жилин Иван Николаевич (с 15.06.1958г.).
Нынешний храм – третий по счету. 21 сентября 2009 года здесь был заложен памятный камень, и настоятель полкового храма Азовской Божьей Матери отец Александр освятил землю под строительство новой церкви. 21 сентября 2013 года клирики Азовского благочиния во главе с благочинным протоиереем Владимиром Удовенко совершили молебен в день первого престольного праздника храма Рождества Пресвятой Богородицы этого села.
Новая церковь была построена за один год. Богослужения с совершением православных обрядов начались в ней с 2014 года. Настоятелем нового храма стал иерей Сергей Александрович Васильев.
Инициаторами создания местной религиозной организации – православного прихода храма Рождества Пресвятой Богородицы выступили Васильев Сергей Александрович, Водолацкий Виктор Петрович, Гончарова Наталья Григорьевна, Комаров Сергей Александрович, Комарова Елена Алексеевна, Котенко Николай Андреевич, Окрушко Андрей Николаевич, Перковец Владимир Иванович, Резец Владимир Васильевич и Сергеев Сергей Сергеевич. Учредительное приходское собрание состоялось 28 сентября 2014 года. А 28 января 2015 года приход был официально зарегистрирован в соответствии с Федеральным законом «О свободе совести и о религиозных объединениях».
Нынешним настоятелем храма является иерей Илия Степанович Кожокарь. При церкви действует библейский кружок и воскресная школа, представители общины принимают активное участие в общественной жизни села.
Более полные сведения об этом храме представлены в моей исторической справке «О Стефанидинодарской церкви Рождества Пресвятой Богородицы и её приходе», подаренной общине верующих в день десятилетия возрождённого храма.