Павел Гайдай родился 15 января 1876 в Измаиле Бессарабской губернии. В следственных делах есть разночтения по поводу места его рождения, и в некоторых документах местом рождения называют Галац (Румыния). Однако у родственников (внучатых племянников, которые проживают сегодня в Измаиле) есть документальные свидетельства о том, что Павел Гайдай был крещен в единоверческой церкви Измаила.
В юные годы Павел Гайдай пользовался духовными советами и наставлениями святого праведного Иоанна Кронштадтского, который завещал Павлу: «Поезжай к протоиерею Ионе Атаманскому в Одессу и следуй по его стопам». Павел — после смерти Иоанна Кронштадтского — выполнил это благословение, приехал в Одессу и служил псаломщиком в одном из городских храмов. Он намеревался принять монашество. Но отец Иона на монашество его не благословил, а подыскал Павлу невесту. В дальнейшем о.Павел никогда об этом не сожалел, был благодарен о.Ионе и своим чадам говорил: «Любите и жалейте матушку, я ею прикрываюсь». О.Павел с матушкой взяли на воспитание двух девочек — Стешу и Веру.
Вскоре после женитьбы Павел был рукоположен в сан диакона, затем в сан иерея и начал свое служение в Петропавловской церкви г. Одессы.
Во время церковных расколов был верен патриарху Тихону.
В 1926 году был переведен вторым священником в церковь Кирилла и Мефодия, а после смерти настоятеля, о.Стефана, «духовно возглавил церковь».
Вскоре он был выселен властями из Одессы на дальний хутор, а затем в село Капаклиевка Шевченковского района Одесского округа. Ежедневно он совершал божественную литургию, служил молебны о болящих, отчитывал бесноватых. И в Капаклиевку съезжались болящие и страждущие от нечистых духов. Храм был переполнен, люди получали исцеление по молитвам отца Павла.
30 апреля 1929 года отец Павел был арестован «за занятие врачеванием, совершение обманных действий с целью возбуждения суеверия для извлечения личной выгоды и ведения контрреволюционной деятельности» и выселен в г. Туруханск Красноярского края на три года. В ссылку за ним поехала матушка, Стеша и Вера (приемные дочери отца Павла) и около двадцати его духовных чад. В Туруханске был сильный голод. Члены общины зарабатывали себе на пропитание тем, что собирали и продавали дикий лук, обжигали известь. Мужчины нанимались валить лес, женщины — стирать белье, чтобы как-то помочь батюшке и выжить самим.
В декабре 1932 года был освобожден. В Одессу он не был допущен и остановился в Киеве, нигде не работал, ходил по церквям, получая материальную помощь от верующих. По некоторым данным, в 1932-1933 годах служил в Ильинской церкви в Киеве.
В начале октября нелегально прибыл в Ленинград для установления связи с «истинно-православными» при Свято-Троицкой церкви. По свидетельству самого о.Павла: «В Ленинграде я остановился у своей духовной дочери Шейнгер Софии Александровны. В ее квартире я устраивал моления, на которых присутствовала Шейнгер С.А., ее дочь Людмила, сын Адриан (в прошлом иподиакон)»
7 октября 1933 года был вновь арестован и посажен в тюрьму «Кресты». К нему в одиночную камеру подселили буйного больного, бесноватого, который, зайдя в камеру, успокоился: батюшка за него помолился и исцелил его. О. Павел обвинялся в том, что «после отбытия наказания за к/р деятельность разъезжал по СССР, нелегально прибыл в Ленинград, установил связь с истинно православной церковью для их активизации» Проходил по групповому делу «Дело священника Гайдая П. И., Колесова А. А. и др. участников тайного церковного сообщества „ИПЦ“. Ленинград. 1933 г.»
12 декабря 1933 года тройкой при постоянном представительстве ОГПУ по Ленинградской обл. был осужден к трем годам ссылки в Туруханский край. Однако в связи с тем, что отец Павел тяжело заболел, в 1934 году его перевели в Акмолинск (ныне Нур-Султан). За батюшкой снова поехали матушка Капитолина, приемные дочери и духовные чада. Здесь они построили низенький домик из самана, где собирались для молитвы.
17 октября 1935 года отца Павла вновь арестовали. Некоторое время он находился в акмолинской тюрьме, там он заболел и лежал в тюремном лазарете. Отрицая свою виновность, отец Павел объявил голодовку, добиваясь освобождения из тюрьмы (по другим сведениям, батюшка пытался не нарушать Рождественский пост. За это над ним издевались и насильно пытались заставить есть скоромную пищу).
В его доме и в домах его духовных чад были произведены обыски, при которых конфисковано большое количество чая, что дало повод обвинить отца Павла и всю общину в том, что он «...организовал поездки за чаем в Одессу и Красноярск с целью его реализации на базаре г. Акмолинска», т. е. в спекуляции. Были арестованы некоторые из членов общины, но, за неимением доказательств, вскоре освобождены. Отец Павел отрицал обвинение в спекуляции.
22 января 1936 года Акмолинский нарсуд осудил отца Павла к десяти годам лагерей. Отбывал наказание в Карлаге НКВД.
По материалам уголовного дела, отец Павел 14 апреля 1937 года совершил побег, но 15 апреля был задержан на Джайла. Причину побега о.Павел объяснял тем, что его грозились убить ограбившие его рецидивисты за то, что он написал заявление по этому поводу. Священник был посажен на пять месяцев в шизо. Там он объявил голодовку и был намерен не прекращать ее до удовлетворения требований. В его камере был произведен обыск, где якобы нашли «под койкой» продукты и вино. О.Павел дал объяснение, что этими продуктами он не пользовался, и потребовал врача для освидетельствования того, что он не принимал пищу.
31 июля 1937 года он был отправлен на Караган, где он уже не мог выходить на работу из-за тяжелого состояния здоровья. Тюремное начальство обвинило о. Павла в том, что он специально вызвал у себя болезнь.
В августе 1937 года отец Павел был вновь арестован, его обвинили в том, что он «среди заключенных систематически вел контрреволюционную агитацию, высказывался против вождей партии и правительства, искусственно поднимал себе температуру для невыхода на работу». Отец Павел виновным себя в предъявленном ему обвинении не признал.
31 августа 1937 года тройкой УНКВД был приговорен к расстрелу.
Расстрелян 5 сентября 1937 года. Место захоронения неизвестно.
