Священномученик Павел Игнатьевич Гайдай родился 15 января 1886 года. Источник называет местом его рождения бессарабский Измаил, хотя в следственных делах встречается и румынский Галац; у родственников, живущих в Измаиле, сохранились свидетельства о его крещении в тамошней единоверческой церкви.

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

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

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

30 апреля 1929 года его арестовали и выслали на три года в Туруханск Красноярского края. За ним поехали матушка, приёмные дочери и около двадцати духовных чад. Кормились чем придётся: собирали и продавали дикий лук, обжигали известь; мужчины шли валить лес, женщины — стирать бельё. Так и держались.

В 1933 году, освободившись, отец Павел перебрался в Ленинград и служил в Георгиевской церкви, но вскоре был арестован снова и оказался в «Крестах». К нему в одиночную камеру подселили буйного больного — тот, войдя, успокоился, и священник помолился о нём. Осудили отца Павла по статье 58-10 и опять отправили в Туруханский край, а из-за тяжёлой болезни в 1934 году перевели в Акмолинск. Община снова поехала следом и построила там низенький домик из самана, где собирались на молитву.

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

В августе 1937 года его арестовали уже в лагере — по обвинению в антисоветской агитации среди заключённых. Виновным он себя не признал. 31 августа тройка вынесла смертный приговор, приведённый в исполнение 5 сентября 1937 года; место захоронения неизвестно. Позднее священник был реабилитирован.

Память священномученика Павла Гайдая совершается 7 февраля и 5 сентября.