Позади малой братской могилы возвышается белокаменная церковь — храм Всех Святых на Мамаевом кургане. На сегодняшний день — это самый «молодой» элемент, находящийся на главной высоте России. Хотя официально храм не входит в памятник-ансамбль на Мамаевом кургане, его силуэт вот уже третий десяток лет формирует вид мемориального комплекса.
Решение о возведении храма на Мамаевом кургане было принято в год празднования 50-летия Победы в Сталинградской битве — в 1993 году. Место для строительства церкви 19 июня того же года освятил лично Патриарх Московский и всея Руси Алексий II, который прибыл в Волгоград вместе с архимандритом Кириллом (Павловым) — участником Сталинградской битвы.
Первоначальным местом размещения церкви должен был стать южный склон Мамаева кургана, там был размещён закладной камень будущего храма, а в 1995 году Патриарх благословил строительство Свято-Владимировского храма — памятника воинской славы. Однако в ходе проектирования место возведения православной святыни было перенесено к Малой братской могиле и в 1997 году Патриарх Алексий повторно дал своё благословение строить храм на новом месте.
Строительство стартовало в 2000 году, официальная дата его начала — 14 октября 2000 года — совпадает с днём Покрова Пресвятой Богородицы. Первый камень в основание святыни был заложен двумя годами позже — 9 мая 2002 года. А спустя ещё два года, 27 сентября 2004-го, — в праздник Рождества Богородицы — был положен последний кирпич в здание храма. Главный купол и крест церкви был установлен вновь на Покров — 14 октября 2004 года.
Храм Всех Святых на Мамаевом кургане был открыт 1 мая 2005 года, к 60-летию Победы в Великой Отечественной войне.
33-метровая белокаменная церковь (38 метров вместе с главным крестом) построена по образцу классических русских церквей, симметричная четырехгранная в плане. Храм имеет пять глав, одна из которых выше остальных, главы увенчаны куполами, напоминающими шлемы былинных витязей.
Расписан храм Всех Святых был в 2025 году, в росписи церкви нашли отражение ключевые исторические события, когда решалась судьба Отечества: Куликовская битва, изгнание поляков из Москва, Бородинское сражение, Сталинградская битва. Общая площадь росписи составляет 1,7 тысяч квадратных метров, иконописцы Палехской мастерской под руководством Алексея Аверина работали над ней около полугода.
Позади церкви расположена 16-метровая звонница с 12 колоколами. Она была построена позже основного церковного здания — в 2013 году.
Авторский коллектив храма Всех Святых на Мамаевом кургане: главный архитектор — Юрий Вадимович Коссович, главный конструктор — Эрлен Владимирович Темников.
