Святые девы-мученицы Еннафа, Валентина и Павла пострадали в 308 году при императоре Максимиане II Галерии (305-311). Святая Еннафа происходила из города Газы (на юге Палестины), святая Валентина была родом из Кесарии Палестинской, а святая Павла - из окрестностей Кесарии.

Первой на суд к правителю Фирмилиану была доставлена святая Еннафа, мужественно объявившая себя христианкой. Ее били, а потом привесили к столбу и начали строгать тело. Святая Валентина, обвиненная в непочитании богов, была приведена в языческий храм для принесения жертвы, но смело бросила камень на жертвенник и обратилась спиной к пылавшему на нем огню. Ее нещадно били и приговорили вместе со святой Еннафой к усечению мечом. После всех была приведена святая Павла, которую подвергли многим мукам, она же переносила их, при помощи Божией, с великим терпением и мужеством. Перед смертью Павла возблагодарила Господа, укреплявшего ее в подвиге, и, поклонившись присутствовавшим христианам, преклонила свою главу под меч.