Позже настоятелем храма был назначен протоиерей Николай Перехвальский. Так случилось, что в начале пятидесятых годов протоиерей Николай Перехвальский по служебным делам был в Елоховском соборе, он обратил внимание на послушника Алексия Байкова и пригласил его приехать в храм святителя Николая Чудотворца в Бирюлёво. В 1955 году после окончания семинарии юноша приехал в Свято-Николаевский храм, здесь он встретил свою судьбу, Прасковью Слогину. Вся дальнейшая жизнь отца Алексия была неразрывно связана с Николаевским храмом - более 55 лет отец Алексий служит в храме Святителя Николая Чудотворца в Бирюлёво.
С горечью вспоминает отец Алексий о событиях 1956 года, в этот год скончался отец Николай, вскоре после его кончины сгорел храм.
Из воспоминаний отца Алексия Байкова: «1 марта храм наш сгорел... Примерно в три часа дня. Ну, я вам скажу, было много версий... Все началось с алтаря. Когда я пришел уже полыхало вовсю... Стою около двери, думаю: «Как спасти?»... Только я хотел, что-то предпринять - меня какая-то сила (оттолкнула) назад, и в это время крыша падает. Если бы секунда... и я бы туда прошел - я бы сам погиб… Господь сохранил меня! Слава Богу, за все!»
По свидетельству очевидцев: «Все это место выгорело. Тяжелые снега лежали вокруг... Пожарные машины не смогли подъехать, а людей не подпустил комсомольский патруль... Не пустили гасить огонь, не дали спасти иконы. (Уцелела лишь одна икона святителя Николая).
Все кресты и деревья возле храма выгорели. Один деревянный крест на могиле матушки Серафимы остался среди пепелища, только чуть-чуть нижний конец креста у земли обуглился. Всего меньше недели не было службы, пока приспосабливали сторожку под храм. Опять началась служба... Властям необходимо было ликвидировать приход. За день до прихода комиссии верующим стало известно, что на следующий день в 10 часов утра прибудет комиссия, которая должна зафиксировать отсутствие храма и, как следствие, отсутствие прихода. Тревожная весть мгновенно облетела всю округу. Верующие пригнали вагон с лесом. Православные мужчины и женщины работали всю ночь, по милости Божией, за ночь успели поставить сруб и укрепили стропила. Утром прибыла комиссия и вынуждена была констатировать, что «строение существует».
По мнению отца Константина Кобелева именно матушка Серафима - создательница нового храма Святителя Николая Чудотворца в Бирюлево: «Батюшка отец Василий Моисеев, еще был молодым священником, пришел к ней (незадолго до её смерти), она ему предсказала, что он будет строить храм...Какие храмы в то время…., когда наоборот только все уничтожалось или закрывалось... И вот то, что она ему, предсказала, что он будет строить храм, это конечно на него повлияло. Иначе как бы он решился сам бы без такого предсказания, без такого благословения приступить к какому-то строительству в то время, когда все священники находились под жестким контролем соответствующих органов и такая инициатива могла кончиться для него очень плачевно. А вот он имел такую веру. Помолился, сходил к ней на могилу, как я понимаю. И потом дерзнул приступить к этому делу. И у него и дальше все так получалось чудесным образом. Потому, что в то время, ну как это можно было храм построить… За все годы советской власти по всей стране было построено только сто храмов, по всей стране, за 70 лет. Причем это, не считая тех, которые были открыты на оккупированных территориях...»
Приведём факты из истории. «Первым сигналом готовящейся новой расправы с Церковью явилось Постановление ЦК КПСС от 7 июля 1954 года, которое призвало Министерство просвещения, комсомол, профсоюзы развернуть беспощадную борьбу с религией». Методы борьбы почти не отличались от методов 30-х годов. Священно служителей особо почитаемых в народе, старались перевести в отдаленные приходы, бывали случаи, когда пастырей переводили с прихода на приход несколько раз. Представители власти могли лишить регистрации любого приходского священника, а затем под разными предлогами отказывали в регистрации новому священнику. Если приход оставался без священника и служб более шести месяцев, его закрывали как не действующий. (Священникам из других храмов обслуживать такой храм запрещалось: «человек должен работать, там, где прописан». Если находились священнослужители, желающие переехать и прописаться рядом с храмом, им отказывали в прописке.)
Нередко пожарная инспекция могла запретить пользоваться храмом, требовали провести генеральный ремонт. В тех случаях, когда бедному приходу не хватало средств на ремонт, решающую роль играл запрет на использование средств «со стороны» благополучных приходов или со стороны епархии... ( В результате всех этих мер количество православных церквей к восьмидесятым годам сократилось вдвое.)