Вскоре после женитьбы Павел был посвящен в сан диакона, затем в сан иерея и начал свое служение в Петропавловской церкви г. Одессы. Во время церковных расколов был предан Патриарху Тихону.

Отец Павел сразу привлек к себе сердца православных одесситов. Он часто служил, говорил прекрасные проповеди, а главное — имел то, чем отличались его духовные наставники — святые праведные отец Иоанн и отец Иона — горячую, живую веру, безграничную любовь к людям, неутомимое трудолюбие. Он самоотверженно приносил себя в жертву ради спасения Христова стада. И люди потянулись к этому молодому, но умудренному Духом Святым иерею.

Духовное влияние отца Павла на народ не могло остаться незамеченным местными властями. Вскоре он был выселен из Одессы на дальний хутор, а затем в село Капаклиевка Тараса Шевченковского района Одесского округа, где продолжал служить Богу и ближним. Ежедневно он совершал Божественную Литургию, служил молебны о болящих, отчитывал бесноватых. И в Капаклиевку со всех близлежащих городов и весей съезжались болящие и страждущие от нечистых духов. Храм был переполнен, люди получали исцеления по молитвам отца Павла.

Матушка Капитолина Дмитриевна была верной его спутницей.
Но служение отца Павла не могло остаться незамеченным богоборческими властями. 30 апреля 1929 года Одесским Окружным отделом ГПУ отец Павел был арестован “за занятие врачеванием, совершение обманных действий с целью возбуждения суеверия для извлечения личной выгоды и ведения к/р деятельности” и решением ОСО при Коллегии ОГПУ УССР от 30 июня 1929 года “подвергнут административному выселению в г. Туруханск Красноярского края сроком на 3 года”.

В ссылку за ним поехала матушка Капитолина и многие его духовные чада, человек около двадцати. Ехали не только одинокие, но и целыми семьями. Стеша и Вера, приемные дочери отца Павла, также поехали в ссылку.

В Туруханске был сильный голод, страдали от комаров. Домик, где жил Батюшка, был расположен под кручей на берегу Енисея. Члены общины зарабатывали себе на пропитание тем, что собирали и продавали дикий лук, обжигали известь. Мужчины нанимались валить лес, женщины — стирать белье, чтобы как-то помочь Батюшке и выжить самим. Но, бывало, по неделям ничего не ели, а Господь всех хранил молитвами отца Павла.

После освобождения, в 1933 году отец Павел переехал в г. Ленинград, где служил в Георгиевской церкви.

В Акмолинск за Батюшкой снова поехали матушка Капитолина, приемные дочери и духовные чада. Здесь они построили низенький домик из самана, где собирались для молитвы.

17 октября 1935 года отца Павла вновь арестовали. Некоторое время он находился в акмолинской тюрьме. Там он заболел и лежал в тюремном лазарете. Когда наступил Рождественский пост, Батюшка старался не нарушать его. За это над ним издевались и насильно пытались заставить есть скоромную пищу.

Отцу Павлу было предъявлено обвинение по ст. 58-10, 11. Отрицая свою виновность по этой статье, отец Павел объявил голодовку, добиваясь освобождения из тюрьмы. Тогда в его доме и в домах его духовных чад были произведены обыски, при которых конфисковано большое количество чая (304 плитки по 250 гр., и 195 плиток по 50 гр.), что дало повод обвинить отца Павла и всю общину в том, что он “…организовал поездки за чаем в Одессу и Красноярск с целью его реализации на базаре г. Акмолинска”, т. е. в спекуляции. Были арестованы некоторые из членов общины, но, за неимением доказательств, вскоре освобождены. Отец Павел отрицал обвинение в спекуляции.

31 июля 1937 года отец Павел был направлен на командировку Караган, где уже не мог выходить на работу по болезни. Тюремное начальство, ссылаясь на показания очевидцев, обвинило его в искусственном поднятии себе температуры для невыхода на работу: “…брал немного хлеба и большую дозу соли, проглатывал и натирал себе под мышками, поднимал температуру, и получал освобождение от работы”.

Отец Павел требовал очной ставки с теми, кто так говорит.

В августе 1937 года отец Павел был вновь арестован. Его обвинили в том, что “среди заключенных систематически вел к/р агитацию, высказывался против вождей партии и правительства, искусственно поднимал себе температуру для невыхода на работу”. Отец Павел виновным себя в предъявленном ему обвинении не признал.
31 августа 1937 года заключением тройки УНКВД по Карагандинской области священник Павел Гайдай был приговорен к расстрелу.

Приговор приведен в исполнение 5 сентября 1937 года.

Место захоронения неизвестно.

Священник Павел Гайдай реабилитирован согласно закону Республики Казахстан “О реабилитации жертв массовых политических репрессий” от 14 апреля 1993 года.

Заикина (Левицкая) Прасковья Григорьевна. (Родилась в 1912 году в с. Гребенники Одесской области):

“О батюшке Павле я услышала, когда мне было 20 лет. Тогда много говорили в народе о том, что появился такой прозорливый Батюшка, которых многих исцеляет, и ехали к нему все из близлежащих городов и селений. Я уговаривала своих родителей, чтобы и меня отпустили съездить к Батюшке в село Капаклиевку. В 1933 году я в числе прочих женщин из нашего поселка поехала к Батюшке. Но когда мы приехали в Капаклиевку, то узнали, что Батюшки уже нет в селе. А через год услышали, что он находится в ссылке в Казахстане, и что матушка Капитолина с Батюшкиными духовными чадами собираются ехать к нему. Я твердо решила ехать вместе с ними.
В это время матушка Капитолина получает письмо от отца Павла, где он пишет: “Матушка, я Вас жду. Пусть и Паша с Вами едет. Мы будем жить, где одни пески и много волков”. Среди желающих ехать в Акмолинск я была одна с этим именем. А впоследствии и второе предсказание сбылось, но коснулось оно только меня. В 1941 году я попала в трудармию, в Джезказганскую область, поселок Изотас, где работала поваром на шахтах. Там, действительно, были одни пески и множество волков, которые зимой заглядывали к нам в окна.

Батюшка просил моего отца остаться в Акмолинске, но отец отказался, сказал: “Лучше я умру с холода и голода дома, но в Акмолинске не останусь”. Так и вышло. Во время сильного голода на Украине в 1935 году отец умер.

Возле Батюшки всегда было очень много народа. В основном это были приезжие из Одесской области — девушки, парни и семейные люди. Все жили по квартирам, а молиться собирались в Батюшкином доме. Отец Павел придерживался строгого устава. Вставал очень рано и перед чтением утренних молитв совершал 1000 Иисусовых молитв с земными поклонами. Он стоял впереди, мы стояли за ним и едва успевали класть поклоны. Сначала 800 поклонов полагали, немного передохнув, еще 200. Затем читали утренние молитвы и служили Литургию. Также и вечером — после Иисусовых молитв читали вечерние молитвы и отходили ко сну. Во время молитвы мы плотно закрывали окна и двери.

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

Часто жарким степным летом всей общиной ходили купаться на реку Ишим (мужчины купались отдельно от женщин). Однажды Юра Рыбаченко не захотел идти купаться со всеми. Батюшке говорят: “Юра не пошел с нами”. А Батюшка сказал: “Скоро Юра совсем от нас отойдет”. И вправду, Юра вскоре скоропостижно скончался. Так сбылись Батюшкины слова.

Первый раз я прожила у Батюшки почти год и поехала домой в Одессу. Немного побыла у родителей и получила от Батюшки письмо: “Дочка, приезжай, сам Святитель Николай тебя зовет”. Письмо это пришло как раз на праздник Святителя Николая. И я снова приехала к Батюшке в Акмолинск.

Уезжать из Акмолинска отец Павел никого не благословлял. Один раз я Батюшке говорю:
— Батюшка, если Вас не станет, я снова поеду в Одессу, здесь жить не буду.
Он отвечает:
— А какой здесь город будет большой, да еще монастырь откроется!
— Что Вы! Здесь кругом только степь да землянки!
А он снова:
— И трамваи ходить будут! Ваше место только здесь!
Я даже с места соскочила:
— Неправда, — говорю, — Батюшка! Какие здесь могут быть трамваи, когда на весь город три автомобиля! (Ездили тогда на верблюдах и на лошадях). А за монастырь и слушать не хочу, это Вы и вовсе преувеличиваете!

Это было сказано в 1935 году. А когда в городе пустили первый троллейбус, а потом в 1970 году и монастырь открыли в честь иконы Божией Матери “Взыскание Погибших”, я вспоминала тогда Батюшкины слова.

Еще Батюшка говорил нам, что придет время, когда церкви и монастыри снова будут строить. Мы спросили: “А кто будет строить?” Он ответил: “Кто ломал, тот и будет строить”.

В 1936 году отца Павла арестовали и посадили в Акмолинскую тюрьму. К нему с передачей пошла Анна Левицкая (сейчас монахиня Евдокия). Батюшка через нее передал мне записку, где он писал: “Родная моя дочь Паша, … я очень рад, что ты меня никогда не оставляешь, помнишь меня. Я тебя не оставлю и всегда буду помнить. Берегись, не поддавайся никакому соблазну, стой твердо, как орел. За маму ты скорбишь, что мама все время больная. Бог благословил ей подвиг болезни, жизнь ее увенчается мученическим венцом. Благословение Параскеве, Анне. Простите меня. С праздником вас, будьте в мире, дети мои”. Я в то время была домработницей у одного судьи. Он вольно со мной обращался и я, получив записку с предупреждением беречься от соблазна, сразу от него ушла. А маме моей Господь вскоре дал христианскую кончину.
Когда Батюшку осудили к 10 годам лагерей, духовные чада остались в Акмолинске ждать его возвращения. В Долинку ему посылали посылки с продуктами. После 1937 года посылки стали возвращаться назад с надписью “След потерялся”, но все же Батюшку продолжали ждать.

Когда мы узнали об этом, то поехали в Караганду взять благословение у батюшки Севастиана на отъезд на родину в Одессу. Но отец Севастиан сказал: “Нет вам благословения отсюда уезжать”. И так, по молитвам этих двух старцев, мы остались жить в Акмолинске”.

Насколько духовные чада любили Батюшку и были преданы ему, можно судить по жизни монахини Аллы (Анны Ивановны Рыбаченко, родилась в 1894 году в с. Копиевка Одесской области).

Анна Рыбачено была молодой, замужней, но бездетной женщиной. По вероисповеданию она была католичкой, но муж ее Кирилл был православным. В 20-е годы Анна тоже прослышала о Батюшке и решила съездить, повидать его. Муж одобрил это намерение, и она поехала. Знакомство с Батюшкой резко переменило ее жизнь. Она перешла в Православие и стала духовной дочерью отца Павла.

Однажды, приехав к Батюшке, она ослушалась его, за что подверглась сильнейшему бесовскому нападению, стала как одержимая. Дали знать ее мужу. Муж приехал, посмотрел на ее чудачества и очень расстроился. Но Батюшка усердно молился и через несколько дней бес из нее вышел.

Анна Рыбаченко, оставшись при Батюшке, часто по его поручениям ездила в разные местности. Так, однажды, она ехала на поезде из Одессы в Киев. Рядом с ней сидели две женщины, которые горячо спорили между собой. Одна из них хулила Бога, а другая что было сил Бога защищала. А Анна всю дорогу слушала их и молчала.
Когда она возвратилась к Батюшке, он ее накормил, а потом сказал: “Как тебе не стыдно! Бедная женщина, как она Бога защищала, из сил выбивалась, а ты молчала и не могла ее поддержать!”

Вспоминают еще такой случай. Как-то, находясь на праздник Успения Божией Матери в г. Киеве, Батюшка сказал Анне Рыбаченко и Марии:

— Сходите на Днепр и наберите рыбы.
— Как мы, Батюшка, наберем, и чем?
Он говорит:
— Руками.
Ради послушания взяли две корзины и пошли к берегу. А там выкинуло на мель множество рыбы. Руками набрали полные корзины.
Прошла неделя. Анна Рыбаченко просит:
— Батюшка, благословите сходить на берег, рыбы набрать.
Он говорит:
— Сходите, посмотрите.

Обрадовались, взяли корзины побольше и пошли. Пришли к берегу, а там ни одной рыбки нет. Посмотрели и пошли назад.

Вскоре отца Павла арестовали и выслали в Туруханск, а затем в Акмолинск. Анна последовала за ним. Мужу она написала в письме, что больше к нему не вернется. Муж, узнав об этом, сильно заскорбел. Но Батюшка написал ему: “Ты не беспокойся, у тебя родится девочка, будешь ее воспитывать”. Так и вышло. Муж женился второй раз, у него родилась девочка. Батюшка в письме поздравил его. А Анна навсегда осталась в Акмолинске.
Потом преподобный Севастиан постриг ее в монашество с именем Алла и скончалась она в Батюшкином домике в возрасте 84-х лет.