Село Бестужево расположено в живописной холмистой местности на правом берегу среднего течения реки Устья, правого притока Ваги (бассейн р. Северная Двина), у места крутого поворота, где общее направление течения реки меняется с северо-западного на юго-западное направление. До 1929 года деревня Бестужевская была волостным центром Вельского уезда Вологодской губернии. Верюжский Введенский погост, находящийся у северо-западной окраины д. Бестужево, получил свое название от первой построенной церкви Введения во храм Пресвятой Богородицы и от речки Верюга, впадающей недалеко от него в Устью.
Небольшая деревянная церковь Рождества Богородицы была заложена 29 сентября 2014 года на бывшем Верюжском Введенском погосте, на месте сгоревшей 9 мая 1994 года деревянной летней "круглой о двадцати стенах" шатровой одноименной церкви. Освятил место и заложил первый камень в основание храма епископ Котласский и Вельский Василий.
К осени 2015 года храм был построен. Регулярные богослужения начались с 2017 года. В 2022 году возле храма была построена звонница на двух столбах.
Клетский храм представляет собой небольшой однопрестольный квадратный в плане сруб, рубленный "в лапу", под четырёхскатной крышей, имеющий одну главу, которая покрыта лемехом. Она стоит на невысоком барабане в виде восьмерика. К основному объёму с востока и с запада примыкают два небольших равновеликих прируба под двухскатными кровлями. На трёхстенный алтарь поставлена главка, также покрытая лемехом. С запада постройка имеет крыльцо с резными столбами и балясинами.
История Введенского погоста тесно связана с обретением мощей святого праведного Прокопия Устьянского. Во второй четверти XVII века на берегу реки Устья близ погоста жители деревни Бестужевская обнаружили на льдине, прибитой к берегу гроб, сплетённый из ивовых прутьев, в котором лежало не тронутое тлением тело, издававшее благоухание. Вскоре после этого, он явился во сне местному жителю Савелию Онтропову и назвавшись Прокопием, велел сделать себе новый гроб. Всё было исполнено в точности. Прокопия положили в новый деревянный гроб у южной стены Введенской церкви, а на месте явления мощей на берегу реки построили часовню. Почти сразу начались исцеления и чудеса от мощей святого. Первое исцеление от мощей было зафиксировано в 1641 году. С тех пор он стал известен под именем праведного Прокопия Устьянского. К месту обретения святых мощей ежегодно, в день памяти святого праведного Прокопия, 8 июля по ст. стилю (21 июля по нов. ст.), в приходе погоста устраивался крестный ход к реке.
Праведный Прокопий Устьянский широко почитался на Севере, особенно в Архангельской и Вологодской губерниях. К нему обращались в различных бедах и скорбях, и он всегда помогал тем, кто просил у него помощи, где бы они ни находились. Сведения о чудесах от его мощей всегда записывались.
К югу от нового храма с 2017 года лежит Крестовый камень. Примерно 115 лет назад жители д. Бестужевской обнаружили его в четырех километрах от Введенского погоста. Он был с очертаниями креста. 25-ти тонный валун размерами 2х1,5 м жители приходских деревень перетащили к погосту и положили между летним Рождественским и зимнем Введенским храмами, близ алтаря последнего. С тех пор ежегодно торжественно совершалось перенесение святых нетленных мощей Праведного Прокопия Устьянского весной из зимней церкви в летнюю и обратно осенью. Во время молебна деревянная гробница с мощами всегда укладывалась на этот огромный валун. Так продолжалось до закрытия в 1939 году прихода. В 1948 году Введенский храм был взорван. Под обломками храма оказался и этот камень. Тогда же мощи святого праведного Прокопия Устьянского были уничтожены.
21 сентября 2017 года, в канун праздника Рождества Пресвятой Богородицы, в с. Бестужево состоялось историческое событие: был поднят из земли и перенесён ближе к храму огромный Крестовый камень. Теперь он является святыней прихода.
6 февраля 2023