Село Бестужево расположено в живописной холмистой местности на правом берегу среднего течения реки Устья, правого притока Ваги (бассейн р. Северная Двина), у места крутого поворота, где общее направление течения реки меняется с северо-западного на юго-западное направление. До 1929 года деревня Бестужевская была волостным центром Вельского уезда Вологодской губернии. Верюжский Введенский погост, находящийся у северо-западной окраины д. Бестужево, получил свое название от первой построенной церкви Введения во храм Пресвятой Богородицы и от речки Верюга, впадающей недалеко от него в Устью. В народе его чаще называли по имени святого - "У Прокопия Устьянского", или просто - "У Праведного".
Первые сведения о Верюжском Введенском погосте относятся к середине XVII века, но, несомненно, погост существовал и раннее. О первых церквах погоста сведений нет, но известно, что деревянные храмы существовали уже во второй половине XVI века. Судя по писцовой книге 1645 года, на берегу Устьи высились тогда три церкви: холодная Введенская «древяна верх», рядом — теплая Флора и Лавра «древяна клетцки» и третья — также теплая Никольская «древяна клетцки с трапезою. ..», а также отдельно стоящая колокольня.
К концу XVII века они «от многолетнего стояния... обетшали и углы у них огнили и обвалились». Благословенная грамота Афанасия, архиепископа Холмогорского и Важского предписывала эти церкви разобрать и на прежнем месте возвести новые.
В 1692 году начали на Введенском погосте строить шатровую Никольскую церковь с тёплой трапезной, а рядом чуть позже — в 1696 году была срублена холодная Введенская церковь.
В 1763 году на месте этой Введенской церкви была построена новая летняя церковь с тем же посвящением, которая была переосвящена в 1809 году (по др. данным - в 1830) в честь Рождества Пресвятой Богородицы, в связи с постройкой на погосте каменной Введенской церкви
"Круглый о двадцати стенах" храм, рубленный "в обло" имел по сторонам света четыре прямоугольных прируба, крытыми поздними трёхскатными кровлями и увенчанными главками. В южном прирубе был освящён придел в честь праведного Прокопия Устьянского, а северном - мчч. Флора и Лавра. Эти придельные прирубы имели свои алтари с пониженной кровлей. Восьмерик основного объёма имел шатровое завершение, рубленное "в реж" и завершённое главой, стоящей на шее. С запада храм был опоясан крытой галереей, незаходящая на северный и южный фасады боковых прирубов.
В 1860-х годах обветшавшая деревянная ограда погоста была заменена на кирпичную с башенками-часовнями, которые к настоящему времени не сохранились.
В 1868 году проводилось "обновление" храма, в результате которого небольшие косящатые окна были растёсаны, перестроена галерея, а сама церковь обшита тёсом и покрашена. Изменён характер завершений прирубов.
В Рождественской церкви хранилась чудотворная икона святителя Николая Мирликийского, перенесённая в храм после закрытия в начале XIX века Никольской церкви, с последующем строительством на его месте каменной Введенской церкви.
Приход был закрыт в 1939 году. В 1948 году разобрали на кирпич Введенскую церковь, а деревянная долгое время стояла бесхозной и медленно разрушалась. В 1978 году рухнул шатёр, а 9 мая 1994 года храм сгорел.
В 2014-2015 годах на месте храма Рождества Пресвятой Богородицы был построен небольшой однопрестольный деревянный храм с тем же посвящением, постоянные службы в котором начались с 2017 года.
История погоста тесно связана с обретением мощей святого праведного Прокопия Устьянского. Во второй четверти XVII века на берегу реки Устья близ погоста жители деревни Бестужево обнаружили на льдине, прибитой к берегу гроб, сплетённый из ивовых прутьев, в котором лежало не тронутое тлением тело, издававшее благоухание. Вскоре после этого, он явился во сне местному жителю Савелию Онтропову и назвавшись Прокопием, велел сделать себе новый гроб. Всё было исполнено в точности. Прокопия положили в новый деревянный гроб у южной стены Введенской церкви, а на месте явления мощей на берегу реки построили часовню. Почти сразу начались исцеления и чудеса от мощей святого. Первое чудо исцеление от мощей было зафиксировано в 1641 году. С тех пор он стал известен под именем праведного Прокопия Устьянского.
Мощи Прокопия Устьянского были неоднократно освидетельствованы церковью. Впервые это произошло 11 августа 1696 года по благословению первого архиепископа Холмогорского и Важского Афанасия, после чего их переложили из ветхого в новый гроб, на котором была сделана памятная надпись. Вторично мощи святого Прокопия были освидетельствованы 28 октября 1739 года по грамоте епископа Архангельского и Холмогорского Саввы. Священники, проводившие осмотр святых мощей, пришли к заключению, что за прошедшее время "никаких частей не умалилось, и тления одеждам никакого не учинилось". Третье освидетельствование мощей праведного Прокопия состоялось 1 августа 1818 года по настоянию крестьянина Федора Кузнецова, получившего исцеление от святыни и дважды после этого посылавшего прошение на имя Государя об оглашении мощей, перенесении их во вновь отстроенную каменную церковь и освящении её во имя праведного Прокопия. Осматривавшие мощи лично епископ Вологодский Онисифор, а также протоиерей Вельского собора Алексей Осокин и священник Иоанн Заостровский сочли огласить их за святые. Однако Святейший Синод решил оставить местное почитание мощей без их оглашения. В результате святой праведный Прокопий Устьянский не был канонизован церковью, как и многие другие местночтимые святые.
До середины XIX века рака с мощами Прокопия Устьянского стояла в приделе Рождественской церкви на полу. В 1852 году в каменном храме начался пожар, угрожавший из-за южного ветра деревянной церкви. Клир и прихожане вынесли святые мощи из церкви и обнесли их вокруг обоих храмов, вследствие чего ветер переменился и опасность миновала. Очевидно, в благодарность за заступничество Прокопия Устьянского после пожара рака с мощами была поставлена на возвышение, к которому вели три ступеньки.
В 1868 году указом епископа Вологодского и Устюжского Павла были установлены служба, акафист, составленный местным священником Вениамином Жаворонковым, и молитва праведному Прокопию Устьянскому. 16 июня того же года, в связи с начавшимся ремонтом Рождественской церкви святые мощи были перенесены в каменную Введенскую церковь. В торжестве приняли участие семь священников и необычайно много для этих мест богомольцев - около шести или семи тысяч человек. К месту обретения святых мощей ежегодно, в день памяти святого праведного Прокопия, 8 июля по ст. стилю (21 июля по нов. ст.), в приходе погоста устраивался крестный ход к реке.
По распоряжению Святейшего Синода 6 июня 1901 года состоялось перенесение святых мощей в кипарисном гробе из старой деревянной гробницы в новую серебряную, которую поставили на прежнее место. Она была сооружена серебряных дел мастером А.Я. Соколовым по рисунку архитектора П.В. Набокова и пожертвована храму статским советником Д.А. Шамаховым. Весной 1908 года в связи с началом капитального ремонта в каменном Введенском храме мощи Прокопия Устьянского вернули в Рождественскую церковь. Тогда же с разрешения Святейшего Синода было установлено ежегодное перенесение мощей на зимнее время в тёплый каменный храм, а на летнее - в холодный деревянный. 18 мая 1910 года усердием прихожан был притащен в церковную ограду громадной величины валун, который положили против алтаря Введенской церкви для остановок и совершения молебна при перенесении мощей святого угодника.
Праведный Прокопий Устьянский широко почитался на Севере, особенно в Архангельской и Вологодской губерниях. К нему обращались в различных бедах и скорбях, и он всегда помогал тем, кто просил у него помощи, где бы они ни находились. Сведения о чудесах от его мощей всегда записывались. Для многочисленных половников, приходивших из дальних мест на поклонение мощам святого, на погосте был построен странноприимный дом. Ныне постройка сохранилась и перестроена под клуб.
В ХХ веке мощи святого Прокопия Устьянского были уничтожены. Но в некоторых приходах до сих пор имеются частицы мощей святого. Так, в Троицком соборе города Онеги Архангельской области находится поклонный крест, в котором хранится частица мощей Прокопия Устьянского.