8 июня 1862 года на средства прихожан была заложена первая однопрестольная церковь в честь апостолов Петра и Павла. Она была деревянной. Освящена 27 апреля 1864 года. Рядом с церковью было и первое кладбище. В 11 выпуске «Донской церковной старины» (город НовочеркасскЪ, «Частная Донская Типография», 1909 год) написано: «В хуторе Каменнобродском Грушевской станицы, Петро-Павловская деревянная церковь была построена в 1867 году. Она сгорела во время грозы 20 мая 1881 года. Настоящая каменная церковь сооружена в 1885 году и посвящена также первоверховным апостолам Петру и Павлу».
Сведения о храме в честь апостолов Петра и Павла были опубликованы в Трудах Областного войска Донского Статистического Комитета, 1908 – Ив. Сулиным, статья "Материалы к истории заселения Черкасского округа".
В материалах Государственного архива Ростовской области, в "Ведомости о церкви Петро-Павловской, области войска Донского Черкасского округа х. Каменно-Бродского" от 1906 года мы узнали следующее: «1. Церковь построена в 1885 году по усердию и на средства прихожан вместо сгоревшей от громового удара 20 мая 1881 года, которая была построена в 1864 году (есть расхождения в датах постройки – прим.автора). Расширена церковь в 1905 году с восточной и северной сторон на средства Грушевской станицы. Кирпичная с деревянным куполом, покрыта листовым железом, ограда железная на каменном фундаменте, при ней колокольня. Освящена 10 ноября 1885 года, а расширенная освящена вновь 24 июля 1905 года. Дом для священника и надворные постройки построены на собственные средства священника Андриана Павловича Поликарпова. У псаломщика собственный дом. Ещё здания: караулка каменная, крытая листовым железом с пристройкой для церковно-приходской школы, которая расширена в 1905 году. Заведующий школой и законоучитель священник Адриан Павлович Поликарпов. Родился священник в Воронежской губернии, сын диакона, в 1876 году окончил курс в Воронежской духовной семинарии по 2 разряду. 26 марта 1878 года Пресвященным Нестором, Епископом Аксайским, рукоположен в священники в данный храм. 31 октября 1884 года награждён набедренником за отличную и усердную службу по гражданскому ведомству. С 25 октября 1886 года Высочайшего утверждения Его Величества Государя Императора состоит пожизненным членом ревнителем Восстановления православного христианства на Кавказе по 4 разряду и имеет серебряный знак святой Нины 4 разряда, медалью за общую народную перепись. 3 февраля 1904 года за 25-летний труд по народному образованию Всемилостивейше пожалован орденом Св. Анны 3 степени и грамотой. Грамоту имеет. Вдов, от роду 54 года» (Клировые ведомости церквей Багаевского благочиния за 1906 год. Государственный архив Ростовской области № дела 11400).
Хуторская власть заботилась о будущем своих детей и поэтому построили рядом с церковью две церковно-приходские школы: мужскую (остатки здания сохранились до сих пор) и женскую. Заведующий школой Андриан Павлович Паликарпов. Одной из первых учительниц женской школы была дочь войскового атамана Мартынова Петра Гавриловича. В 1904 году в сей церкви совершено было треб: крещений – 139, браков повенчано - 22, погребений – 89. Поселковый атаман урядник Тимофей Дмитриевич Коцупеев.
«В богоборческое время храм несколько раз закрывался и окончательно был закрыт в 1961 году, в году хрущевских гонений на Церковь. До недавнего времени в здании поруганного храма находился склад химикатов. И лишь три года назад милостью Божией, стараниями местных жителей и попечением жертвователей началось восстановление поруганной святыни: сделан ремонт притвора, где окормляющим храм иереем Андреем Супруновым совершаются молебны, на одном из уральских заводов отлит и установлен колокол на колокольне весом 40 килограмм, ведутся работы по ремонту алтарной части. Нынешним летом изготовлен крест высотой 1,2 метра, который пока установят на алтарной части храма» (Статья Ольги Изотовой, информационный канал города Шахты).
В годы Великой Отечественной войны храм уже не работал. С ноября 1941 года по весну 1942 года в нем покоились тела убитых курсантов РАУ, погибших на кургане Бабачий у хутора Каменный Брод. Эмиль Сокольский в статье «Потерянный Брод», газета Крестьянин от 29 марта – 4 февраля 2003 пишет: «Старожилы рассказывали, что в 1943 году, когда немцы отступали, взошёл офицер на паперть отдать указание взорвать церковь – но вдруг упал и насмерть зашиб голову о ступени. И немцы, убрав взрывчатку, поспешили от греха подальше...».
В 1960-х годах по указанию местных властей здание церкви было частично разрушено. В том, что осталось, был устроен спортивный зал, а после строительства новой школы храм достался колхозу, потом совхозу, которые использовали его как мастерские, складское помещение для хранения химикатов. К девяностым годам остались одни только стены.
В начале 90-х годов прошлого века было принято решение перестроить оставшееся здание в клуб, но из-за отсутствия средств, строительство (слава Богу) было прекращено в самом начале. В 1997 году церковь Петра и Павла начали реставрировать, но работы вскоре были приостановлены. В 2008 году восстановление храма вновь началось. Изначально сооружение было крестообразной формы, но от двух приделов остались лишь фундаменты.
https://ok.ru/moykhutor/topic/71117047406592
