Приход храма Владимирской иконы Божией Матери в Малой Кудьме был основан в октябре 2001 года, когда начались проектные, изыскательные и строительные работы. 15 января 2004 года состоялось малое освящение деревянного храма в честь преподобных новомучеников Вениамина и Никифора, и была проведена первая Божественная Литургия. Архимандрит Вениамин (Кононов), последний настоятель Соловецкой обители, и его келейник иеромонах Никифор (Кучин) были жестоко убиты (сожжены заживо) в лесной избушке у реки Лодьма в районе Волкоозера на Пасху 1928 года.

27 сентября 2004 года был отслужен молебен перед началом закладки фундамента нового каменного храма Владимирской иконы Божией Матери в Северодвинске. Спустя два года на храм установили кресты и купола. Пять купольных конструкций были изготовлены на специальном предприятии в Волгодонске, а их общий вес составляет 15 тонн. Главный колокол храма, названный «Благовестник», весит 51 пуд.

23 ноября 2008 года состоялось великое освящение храма Владимирской иконы Божией Матери в Северодвинске. Строительство велось при активном участии горожан, многие из которых жертвовали средства на его возведение. Каждый житель мог внести свой вклад, приобретая именные кирпичи, и теперь их имена вписаны в фасад храма.

Местночтимый список Владимирской иконы Божией Матери изначально находился в селе Меландово Емецкого уезда Архангельской губернии в деревянной церкви XVI века, освящённой в честь Святой Троицы. В советское время церковь была закрыта, разграблена и осквернена большевиками, и в таком полуразрушенном состоянии она остаётся до сих пор.

Некоторые христианские реликвии были чудом сохранены местными жителями, включая храмовую Владимирскую икону Божией Матери, которая находилась у Яковлевой Валентины Макаровны и её дочери Мининой Веры Анатольевны. В 2001 году они передали святыню новообразованному приходу будущего храма Владимирской иконы Божией Матери в Северодвинске.