Храм во имя Всех Святых на территории Тольяттинского городского кладбища был задуман в начале 2000-х годов по инициативе благочинного. Администрация кладбища выделила участок под строительство, и началась реализация проекта. 5 ноября 2002 года было освящено место под строительство, а 27 марта 2003 года - купола храма. С этого времени церковь начала действовать, сначала как приписная к Благовещенскому приходу микрорайона Фёдоровка, а впоследствии как самостоятельный приход.
9 апреля 2006 года архиепископ Самарский и Сызранский совершил великое освящение храма и первую Божественную литургию. Образцом для постройки послужила храм-часовня в честь Державной иконы Божией Матери при Храме Христа Спасителя в Москве. Здание выполнено из дерева в форме равностороннего креста с шатровым завершением и пятью куполами.
Храм имеет срубовую конструкцию с подчёркнутой аскетикой фасадов, которую смягчают резные наличники и архивольты. Все части - алтарь, притвор, боковые приделы - равны по форме и объёму. Окна прямоугольные с арочными обрамлениями, перекрытия цилиндрические, расширяющиеся по краям. Главный вход традиционно расположен с западной стороны. Колокольня и внутренние галереи отсутствуют.
Главной доминантой интерьера является деревянный иконостас, украшенный резьбой. Особое место занимают две большие иконы, расположенные на стенах: Всех святых (левая стена) и Страшного суда (правая стена). Храм освящён в честь Всех святых, память которых отмечается в первое воскресенье после Дня Святой Троицы.
Храм несёт особое служение - постоянное молитвенное поминовение усопших. Здесь регулярно совершаются панихиды, литии, отпевания. Храм открыт ежедневно: с понедельника по субботу с 09:00 до 15:00 служатся молебны, панихиды и частные требы; в воскресенье совершается Божественная литургия, храм открыт с 09:30 до 15:00.
