Московский парк Победы, по сути, является блокадным мемориалом. Место массовых захоронений погибших во время блокады жителей Ленинграда требовало увековечивания памяти о погибших. 22 июня 1996 года в парке установили деревянный Поклонный крест на месте выезда вагонеток из заводских печей на узкоколейные пути. Памятная табличка гласит:
«Здесь были печи завода-крематория; прах сотен тысяч воинов и жителей блокадного Ленинграда покоится в прудах, газонах, под вашими ногами; Вечная им память!».
Под крестом захоронена капсула с землей, взятая из разных мест с берегов Адмиралтейского пруда.
В 2005 году, после признания братской могилы в Московском парке Победы воинским захоронением №107, встал вопрос о возведении храма. Однако далеко не всем петербуржцам пришлась по душе идея храмостроительства в парке. Некоторые ветераны войны выступили против, опасаясь что парк, создававшийся самими же ленинградцами для того, чтобы в нем отдыхать и развлекаться, заниматься спортом и физкультурой, не превратился в зону молчания. В том же году мемориальная часть Московского парка Победы была определена как охранная зона особого режима. Ее границы – Гвардейская аллея с севера, Бассейная улица – с юга и Московский проспект с запада. После определения границ споры о строительстве затихли. Однако мемориальная часовня, позднее преобразованная в храм, была построена лишь в 2010 году.
Проект новой церкви, созданный архитектором С. М. Шустерманом в традициях петербургской храмовой архитектуры, органично соединён со строгой классической стилистикой парка и павильоном скорби, расположенном на берегу Адмиралтейского пруда. Храм прекрасно вписался в окружающий пейзаж и стал не только духовной, но и художественной доминантой мемориальной зоны. От начала строительства до освящения храма прошло всего четыре месяца.
7 мая 2010 г. храм в честь Всех святых, в земле российской просиявших был освящен митрополитом Санкт-Петербургским и Ладожским Владимиром. С этого момента в храме ежедневно совершаются богослужения в память о погибших во время блокады Ленинграда. В памятные дни проходят торжественные панихиды и крестный ход.