Святой Павел Гордовский родился в 1880 году в г. Радомышле (ныне Житомирская область на северо-западе Украины). Происходил он из семьи священнослужителя – отец был диаконом местного Троицкого собора. У Павла было двое братьев и сестра.

Образование будущий священник получил в духовной семинарии в Киеве, которую окончил в 1904 году. Следующие несколько лет работал учителем в нескольких школах уезда.

В 1909 году Павел женился и вскоре принял сан священника. Десять лет он прослужил приходским священником на нескольких приходах уезда: Рождество-Богородичных церквях с. Заньки и с. Гуменники, Параскевинском храме с. Старостинцы.

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

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

После прихода в Старостинцы красноармейцев, сторонники новой власти стали оскорблять отца Павла и надругались над ним: отобрали крест и угрожали смертью. В 1919 году святого арестовали по обвинениям, якобы он являлся противником советской власти. На тот момент в его доме осталась беременная матушка с тремя малолетними детьми.

Иерей Павел был доставлен в здание Волынской чрезвычайной комиссии в Житомире. Проводя допрос, следователь счел священника главным оплотом контрреволюции в районе и ярым врагом советской власти.

После ареста за священника пытались заступиться жители Старостинец. 141 человек поставили подписи под заявлением о невиновности в предъявленных ему обвинениях и обращением об освобождении. Власти расценили это как собрание «темной массы», поэтому оно не возымело результата.

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

В 2013 году Синод УПЦ причислил его к местночтимым святым Житомирской епархии. Тогда же обрели мощи, которые ныне почивают в Житомирском кафедральном соборе Житомира Преображения господня.

В 2018 году часть мощей была передана в дар Иоанно-Предтеченскому собору Бруклина (г. Нью-Йорк).

Память св. Павла Житомирского отмечается 25 августа.