Считается, что своим рождением станица Анастасиевская обязана легендарному полководцу Суворову. Но есть и другая легенда.

Шел 1860 год. В ненастный осенний день купец Еремей вез кожевенный товар. По дороге близ Еммануиловского укрепления у телеги сломалось колесо. Кругом плавни, безлюдье. На носу зима, а на возу жена, которой рожать со дня на день. Делать нечего, распряг купец коней, вырыл землянку на берегу реки Давыдовки. А вечером 29 октября (по старому стилю) родилась у него дочь, и назвали ее Анастасией — в честь преподобной мученицы Анастасии Римляниной, память которой отмечалась в этот день. Потому станицу и назвали Анастасиевской.
 В 1886 году станичники начали строить храм. Денег не жалели, и в 1889 году церковь была готова к освящению. Придел освятили в честь святой преподобномученицы Анастасии Римляниной. Второй придел — в честь великомученика Михаила Тверского. История сохранила имя священника, служившего в Свято-Анастасиевском храме, — отца Василия, происходившего из казачьего сословия. Принял он участие и в строительстве школы. Дело в том, что станичный атаман отказывался выделять деньги и землю под постройку школы для иногородних. О решении вопроса школьный архив свидетельствует: «Выручил хитрый поп Василий, который предложил за крещение казака в церкви брать 50 копеек, а за крещение иногородних — один рубль. 50 копеек шли на строительство школы. Более чем за 10 лет собрали деньги, но места для строительства всё не было. Выручил тот же Василий, который выделил на церковном дворе небольшой участок. И в 1902 году была построена школа, которая стала называться церковно-приходской.
Отец Василий Мухин многие годы был благочинным округа и инспектором школ, его деятельность отмечена многочисленными государственными и церковными наградами.
Но пришли другие времена. В 1923 году газета «Красное знамя» написали: «2 апреля арестовали священника церкви ст. Анастасиевской Мухина за антисоветскую пропаганду, осужден по 2 ст. Уголовного кодекса». В 1932 году церковь закрыли. Старожилы вспоминают, что когда закрывали храм, женщины рыдали и украдкой спасали иконы, лампады, книги. Были и такие станичники, которые в обшей суматохе пытались прихватить любую вещь, пригодную в хозяйстве, — доску, лист железа. Церковную ограду разобрали по частям.
Весной 1943 года, после освобождения станицы от фашистов, когда все силы были брошены на прорыв гитлеровской «Голубой линии», деревянный храм, простоявший более полувека, был разобран до основания. Бревна и кирпичи пошли на отмостку дороги, доски и другой сподручный материал — на укрепление окопов. В послевоенные годы на фундаменте храма, сровняв с землей могилы именитых станичников, захороненных внутри церковной ограды, активисты построили большой клуб с кинозалом. Но здание быстро перешло в разряд аварийных и в начале восьмидесятых годов было снесено. Напротив выстроили Дом культуры, а на месте, где стоял храм, образовалась площадь, поросшая травой. Остатки церковного фундамента видны и поныне.
В 1990 году по инициативе станичников для нужд православной общины выделено здание бывшего колхозного детского сада и территория, прилегающая к нему. Сегодня решается вопрос о строительстве храма на его историческом месте, в центре станицы. Документы и проект готовы, дело, как всегда, — за финансированием. Но станичники верят, что с помощью святой Анастасии всё у них получится.

О.Ластовка, учитель основ православной культуры СОШ №28 ст Анастасиевской.