Существует устное предание, что в середине 20 века, проезжая через Всеволожск, ныне прославленный в лике святых архиепископ Лука (Войно-Ясенецкий) обратил внимание на то место, где ранее находился летний кинотеатр, а сейчас стоит наш храм и сказал: «Хорошо бы здесь быть храму».
В 1995г по инициативе местных жителей микрорайона Бернгардовка, при содействии фонда «Дорога Жизни» и фирмы «Синай», был поднят вопрос о постройке храма. На тот момент времени во Всеволожске проживал потомственный священник, протоиерей Димитрий Амбарцумов внук священномученика Владимира Амбарцумова, который и взял на себя духовное окормление местных жителей.
Есть упоминание, что некто из тех, кто прилагал усилия для того чтобы в Бернгардовке появился храм, предпринял в конце 1994 года паломничество на остров Залит к известному в православной среде старцу Николаю Гурьянову, который также благословил начинаемое дело.
В 1995 году было подано прошение митрополиту Иоанну (Снычеву) на строительство храма. В этом же году, в концертном зале у Финляндского вокзала, где с лекцией выступал митрополит, ему были преподнесены два проекта будущего храма. Из двух предлагаемых проектов он утверждает проект деревянного храма и преподает свое благословение на его строительство.
При финансовой поддержке Юрчука Александра Лукича, Васина Михаила Александровича и Михайловой Людмилы Яковлевны начинается возведение стен. Во время строительства храма проводятся регулярные молебны. Отец Димитрий Амбарцумов полностью берет под свое руководство строительство нового храма.
Однажды, место строительства посетил священник, внук святителя Иннокентия Иркутского и в дар храму была преподнесена икона святого с частицей мощей.
С 1998 года в храме начинают совершаться Божественные литургии священниками Троицкой церкви г. Всеволожска, среди которых более всего запомнился прихожанам протоиерей Александр Мирошниченко. До 2001г храм является приписным к Троицкой церкви.
В 2001 г приход храма обратился с прошением к митрополиту Владимиру (Котлярову), чтобы у нового храма был свой настоятель. Митрополит Владимир удовлетворил просьбу прихода и в этом же году его указом настоятелем в храм назначается священник Алексей Амбарцумов, брат Димитрия Амбарцумова.