Первое здание Рождество-Богородицкой церкви было деревянным и возведено основателями станицы, черноморскими казаками сразу по прибытии на место поселения в 1794-1796 гг. Каменное построено в 1833 году тщанием прихожан.

В формулярной ведомости за 1843 год указывается, что престол в церкви один – во имя Рождества Пресвятой Богородицы. По клировой ведомости за 1915 год при церкви числились: священник Максим Иванович Карпов, псаломщики:  Иоанн Михайлович Кубанский и Михаил Васильевич Кондратов. Церковным старостой был – Григорий Пименович Коваленко.
Прихожан в церкви: духовного звания – 8 душ мужского и 7 женского пола; военных 2947 душ мужского, 3066 – женского пола; 54 человека мещанского сословия. Всего прихожан храма на 1915 год было 6637 человек.
         Храм в станице Полтавской постигла участь многих других храмов в СССР. В 1932 году каменный храм Рождества Пресвятой Богородицы был разрушен, поэтому до 1942 года в станице богослужения прекратились. С осени 1942 года богослужения вновь возобновились и проходили в здании бывшей больничной прачечной.

В 1949 году православные жители станицы Полтавской (в то время Красноармейской) купили участок земли, с находящимся на нём домом дореволюционной постройки. Это здание было преобразовано в храм, где и совершались богослужения. В 1984 году Приходской совет совместно с настоятелем приняли решение о проведении капитального ремонта храма, в связи с его обветшанием. Но, проведя тщательные исследования, выяснилось, что капитальный ремонт не решит возникших проблем и, поэтому родилось решение о строительстве нового храма. В 1985 году начались строительные работы, прервавшиеся почти на два года из-за господствовавшей в то время коммунистической идеологии, а затем продолжившиеся до 1991 года. В 1991 году храм был завершен и 26 октября, в праздник Иверской иконы Божией Матери, был торжественно освящен архиепископом (ныне митрополит) Краснодарским и Кубанским Исидором. В 1995 году, с благословения Высокопреосвященнейшего Исидора, в храме Рождества Пресвятой Богородицы начались работы по росписи стен, которые продлились до 2000 года. Храм однокупольный, однопрестольный, с каменным иконостасом. С южной и западной сторон, над боковым и центральным входами, располагаются мозаичные иконы Спасителя и Божией Матери соответственно.

В 1990 году настоятелем храма был назначен отец Симеон, который в 1991 году завершил строительство нового храма. 26 сентября 1991 года храм был освящён.

До разрушения в 30-х годах ХХ века церковь находилась на территории центральной части нынешнего станичного парка.

Нынешнее здание Храма Рождества Пресвятой Богородицы расположен по адресу: станица Полтавская, улица Красная,171.