Мемориальный комплекс расположился на месте братских захоронений времен Великой Отечественной войны. Первые захоронения военнослужащих появились осенью 1941 года после бомбежки железной дороги и переправы через реку Дон. Позже появились еще два захоронения с бойцами, погибшими в боях за Аксай в ноябре месяце во время первой оккупации и после освобождения станицы. Ещё два захоронения появились летом 1942 и в феврале 1943 годов.
Первый памятник появился на месте нынешнего мемориала в 1947 году. Это был деревянный обелиск в виде пирамиды со звездой на вершине.
10 июля 1949 года в сквере на центральной площади Героев был открыт бронзовый бюст Николая Дмитриевича Гулаева-лётчика-истребителя, дважды Героя Советского Союза. Его имя носит МБОУ СОШ № 1 Аксайского района и военно–исторический комплекс городского музея.
9 мая 1975 года торжественно открыли Мемориальный комплекс. Вечный огонь зажег Герой Советского Союза Алексей Хрисанфович Рой, председатель ветеранской организации района.
14 февраля 1983 года состоялось торжественное открытие мраморных плит со списками не вернувшихся с войны аксайчан.