Название села – Анастасиевка – вызывает споры у историков, исследователей и жителей Матвеево-Курганского района на протяжении многих лет. Все они сходятся в одном - хутор на этих территориях основал Адриан Карпович Денисов в 1806 году. Он заселил эту местность крестьянами, ранее проживавшими в Павловском уезде Воронежской губернии. Краеведы озвучивали версию, что хутор был назван Денисовым Анастасиевкой в честь жены Анастасии, в браке с которой было рождено три сына и дочь. Однако есть и другая версия, полностью опровергающая первую. В ней уверены жители хутора Анастасиевка, и их доводы подтверждаются фактами в литературе. В книге «Донские дворянские роды», датированной 1902 годом, указывалось, что основатель села был похоронен на его территории. Но его женой была не Анастасия, а Мария Персидская, которая происходила из богатого казачьего рода. Их брак не был счастливым, потому что был заключен без любви. У Денисовых была единственная дочь Екатерина, а ее мужем был полковник лейб-гвардии казачьего полка Иван Афанасьевич Егоров. Не известно, сколько детей было у Екатерины Денисовой и ее мужа, но одного из них точно звали Адриан. Он сохранил воспоминания своего деда, передал их литератору Адаму Петровичу Чеботарёву для того, чтобы те публиковались в журнале «Русская старина». Вторым внуком Денисова мог быть есаул Андрей Егоров, который упоминается в документах как владелец земли на здешней территории. А вот мать Денисова звали Анастасией Ивановной. В честь нее и было названо село. Сохранились ведомости, что могилы жены, дочери, зятя и самого Денисова располагались рядом с церковью, хотя после революции 1917 года могила атамана была уничтожена[2].

Сама церковь была построена в 1824 году и получила название Церковь Покрова Пресвятой Богородицы.

Есть основания полагать, что могила атамана была случайно найдена в 1960-х годах при прокладывании водопровода. Работы проводились близ церкви, когда ковш экскаватора случайно задел захоронения. В них обнаружилась богатая парчовая одежда. Находку афишировать не стали, место зарыли, а в 1980-х в этом месте асфальтировалась дорога