Всесвятский храм расположен на территории городского кладбища «Марьина Роща», устроенном в 1939 году на городской окраине, в одноименном лесном массиве.
Это место известно с XVII века, в документах того времени оно носит название «пустошь Марьино». По преданию, здесь жила атаманша Марья, которая разбойничала на дороге, ведущей в Москву. В 1965 году здесь был открыт мемориал воинской славы в честь воинов, скончавшихся в госпиталях города во время Великой Отечественной войны 1941 – 1945 годов. На кладбище похоронены многие деятели науки и искусства, видные военачальники Нижнего Новгорода. По некоторым сведениям, здесь есть могилы священнослужителей.
В 1997 году на кладбище открыт мемориал в память воинов-нижегородцев, павших 6 марта 1996 года в Чечне и погребенных в Марьиной Роще.
В 2002 году открыт мемориал в память моряков-подводников, трагически погибших на атомной подводной лодке «Курск» в августе 2000 года и погребенных на этом кладбище.
Строительство храма началось с 1997 года, толчком к этому послужили трагические события в Чечне, когда в бою 6 марта 1996 года пали смертью храбрых 10 сотрудников Волго-Вятского РУБОП, регионального Управления по борьбе с организованной преступностью. Близкие и сослуживцы павших воинов решили увековечить их светлую память строительством церкви.
Во главе инициативной группы стояла В. А. Кудрявцева, мать погибшего воина. В 1998 году был заложен первый камень в основание будущей церкви, и 25 декабря 1999 года храм был освящен. Вначале храм был небольшим по размерам, полезная площадь 36 кв. м и не мог вместить всех молящихся. Трудами и заботами попечительского совета, в который вошли многие известные лица города и области, руководители предприятий, частные предприниматели, ко дню Всех Святых в 2001 году был построен притвор, и богослужения стали совершаться в просторном храме.
Была расширена и соединена с храмом звонница, состоящая из восьми колоколов весом от 8 до 500 килограммов.
К ноябрю 2002 года была завершена роспись стен молельного зала церкви, руководил работами художник-реставратор Н. Е. Юшков. Фасад храма украсили керамические иконы, выполненные народным художником России В. П. Гришиным.
