Для исполнения Высочайшего повеления в Белогорские пещеры была снаряжена комиссия, которая состояла из Павловского протоиерея Афиногена Печерского, Белогорского протоиерея Иоанна Ставрова и Воронежского губернского архитектора Амвросимова. Когда комиссия, прибыв в пещеры, объявила Шерстюковой Высочайшее соизволение продолжать труды в пещере, Мария Константиновна приняла эту милостивую волю Государя с подданническим благоговением и, сделав пред св. иконами несколько земных поклонов, просила Предвечного о ниспослании долголетнего здравия Всеавгустейшему Монарху и всей Императорской фамилии. В то же время она выразила желание, чтобы предположенная в пещере церковь была во имя Св. Благоверного Великого Князя Александра Невского.

Комиссия признала, что твердость мелового грунта, чистота и легкость воздуха в пещере делают удобным устройство здесь церкви. Смета на устройство церкви была определена архитектором Амвросьевым в 5738 рублей 42 коп. На вопрос комиссии, может ли Шерстюкова устроить церковь на свой счет, Мария Константиновна ответила, что это невозможно. Тогда Епархиальное Начальство сократило расходы до 2500р., решив не устраивать колокольни, как это предполагалось до этого, не покупать ризницы и утвари. Богослужение в пещерной церкви временно должен был отправлять не особый причт, а духовенство Троицкой Белогорской церкви, из этой же церкви решили заимствовать ризницу и утварь.

Князь Голицын предлагал Марии освятить церковь Св. Троицы или в воспоминание Воздвижения Честнаго Креста Господня, но Мария осталась при своем мнении, правда решила, что будет лучше в иконостас поместить иконы Св. Троицы и Воздвижения Креста Господня [13] . 30 августа церковь была освящена, о чем 13 ноября 1819 года был уведомлен князь Голицын. Доходы церкви были значительны, и к 1824г. скопилось 4625р., которые по Высочайшему соизволению были обращены в пользу бедных духовного звания. В 1820 году, по просьбе Марии, к пещерной церкви определили особого священника Илию Мишина и причетника, а вскоре появились диакон и пономарь. Из священников этого времени известны еще Диомид Андреевский, Руднев и другие. Незадолго до смерти Марии (22 июля 1822г.) около пещер поселились шесть казацких девиц: Прасковья Выпряжкина, Анна Капылова, Прасковья Шумилина, Настасья Калыгова, Варвара Шишкина и Анна Шумилова.

К делу №5355 из фонда канцелярии Обер-прокурора Св. Синода приложено письмо Марии Шерстюковой, которое приводится здесь дословно, с сохранением орфографии подлинника:

"Сиятельный князь Александр Николаевич. Милостивый государь заступник и покровитель невинных, а особенно гонимых света сего суетного. Небезъизвестно полагаю Вашему сиятельству, что назад тому около пяти лет, как по повелению Всеавгустейшего Монарха свыше данному дозволено Воронежской губернии Острогожског уезда в слободе Белогорье построить церковь в пещере, которую я по усердию своему обрабатывала около сорока лет. Для прославления имени Божия и Всеавгустейшего Монарха церковь в оной пещере выстроена, в которой для прославления имени Божия и Нашего монарха за столь отеческое попечение стекается народное собрание как в какой-нибудь монастырь и почти беспрестанно завидуя, ревнуя сему враг общий супостат, желающий расторгнуть или паче сказать уничтожить сие Монарха нашего и мое благое намерение, клонящееся к души спасения не только мне одной но и многим. Злость, зависть и самое недоброжелательство той же слободы Благочинного Протопопа Иоанна Ставрова желающего отклонять и совершенно прекратить ход не только в означенную пещеру, но и в храм, по повелению Божия и Всеавгустейшего монарха устроенный. Недоброжелательство оного благочинного Ставрова напред сего около двадцати лет делаемоя видно из его представляемых на меня Репортов, по коим и пещера была завалена чрез свецкое начальство несколько раз; при построении по высочайшему повелению в оной пещере церкви более и более стекается так, что в оную церковь, при коей находится означенный Благочинный гораздо и можно сказать в десятеро меньше стекается, нежели в новь устроенную церковь, представил означенный благочинный Ставров в сем году к преосвященному Епифани Епископу Воронежскому и Черкасскому о каком-то даже и непонятном для меня чинимом якобы мною суеверии и живущими близ оной пещеры своими хижинами девицами из различных мест по одному только уверению Бога спасителя и угодников его , написанному в священном писании тако: аще кто хощет по мне идти да отвержется себе и возьмет крест свой со вторицею приемаю" - сии пришедшие и водворившиеся своимии хижинами жить близ оной пещеры по гласу свыше им полагаю данному - им ничего не оставалося как, истощив все свое имение на постройку хижин, прославлять имя Божия, прославлять и Всеавгустейшего Монарха за дозволение устроить в оной пещере церковь, с коиим по приклонении почтенным слезами сим начертании с моими сотрудницами всепокорнейше прошу уважить 90летнюю старуху и близ оной пещеры для прославления имени Божия построенных старице они просили и Гражданского Губернатора и преосвященного, но все их моления и прошения неуважены, а остались тщетны и мне по свецкой части по сношению архиерея велено из своих жилищ убогих хижин ими самими и своим коштом выстроенным удалиться. К душевному прискорбию мне им; а протчим к соблазну. Сиятельнейший князь, есть и когда, то теперь молю и прошу с вышеописанными моими сотрудницами от лица до земли предписать через кого следует их не притеснять и позволить им жить по прежнему в своих выстроенных хижинах для прославления имени Божия и Всеавгустейшего Монарха и Вашего Сиятельства. О сем просит Воронежской Губернии Острогожского уезда слободы Белогорья Старица Марья Шерстюкова" [14] .

О.В. Шамаев в "Летописи Белогорского Воскресенского монастыря" пишет, что эти самые девицы "составили два прошения: одно от имени Марии, другое от себя, с приложением просительных писем от полковницы из войска Донского Марфы и полковничьей дочери Анны Сычевых, - об удалении от заведования пещерною церковью протоиерея Иоанна Ставрова, почитая его наглым утеснителем. Пещеры действительно были переданы в ведение благочинного протоирея Сцепенского, при чем назначено было следствие по содержанию жалобы. Но еще до начала следствия жалобщицы удалились из пещер неизвестно куда, а Мария показала, что они поселились в пещерах самовольно и что прошение подано ими от ее имени ложно, сама же она обид от протоирея Ставрова не терпела". Так может быть, письмо Шерстюковой, приложенное к делу №5355, неподлинно?

Вообще, отношения Марии Константиновны и Иоанна Ставрова остаются загадкой. Одни источники говорят об их непримиримой вражде, другие опровергают этот факт.

А. Данской в 1876 году писал: "Благочинный Протоирей Ставров строго преследовал пещерницу и её сотрудников, наблюдая неослабно, чтоб отнюдь не было рытия пещеры. Однажды он отправился обозреть: не производятся ли в пещере вновь работы; вдруг на дороге, неизвестно от чего, езжалые смирные лошади бросились стремглав бежать и свалили его из экипажа в глубокий обрыв, из которого, от чрезвычайного ушиба, вытащили почти в беспамятстве. С этого несчастного приключения Ставров дал клятву не только не преследовать пещерокопательницу, но ещё способствовать ей довершить предпринятое ею дело".

Что касается казачек, то, как докладывал 31 августа 1822 года Голицыну Воронежский вице-губернатор Дирин по указу Воронежского Губернского правления, последовавшему по отношению Духовной Консистории земским судом, еще до смерти Шерстюковой девицы были высланы, и куда они отправились неизвестно [15] .

Мария с 1798г. по 1818г. имела собственную хижину на хуторе Кирпичи, в полуверсте от пещер. Но в 1818г., когда Высочайше позволено было продолжать труды в пещере, она устроила себе близ пещеры небольшой домик, две девицы прислуживали ей. Мария в свои 80 лет не могла уже заниматься копанием пещеры, а только часто приходила в нее, поощряла богомольцев и указывала управляться с инструментами. Когда в 1818г. в первых числах мая получено было известие, что Государь Александр Павлович проездом из Новочеркасска будет ночевать в городе Павловске, в народе разнесся слух, что Император непременно посетит и пещерницу Марию. Поэтому за несколько дней при входе в пещеры в меловой горе была выкопана довольно просторная келья, где Мария намеревалась принять Государя и беседовать с ним. Но Александр в пещере не был, хотя при обозрении Павловска и окрестных видов не мог не заметить меловых гор. Среди народа ходила молва о чудесах Марии. Эти рассказы были занесены в рукопись под заглавием " Город Павловск и окрестности его" [16] . Люди говорили, что в пещере своей Мария всегда слышит ангельское пение, ходит иногда по воздуху, осиянная небесным светом, проповедует слово Божие и приводит приходящих к ней на путь истинного богопознания. Это опять настроило власти против Марии - было наряжено новое следствие. Но оно, как и прежние, окончилось ничем. Мария все отрицала. 12 июля 1822 года В.Р. Марченко (Правитель дел Комитета Министров ) написал князю Голицыну, что "Сия старуха Шерстюкова как от Благочинного дано знать мне прошедшего июня 22-го дня помре, а потому думать можно, что злоупотребления и суеверие в донесении моем…описанные со смертью оной старухи Шерстюковой сами собою вскорости прекращены будут" [17] .