По именам известны 52 мученика, пострадавшие в Палестине в 303–311 гг. В 307 г. была разгромлена кесарийская школа; её глава пресвитер Памфил был брошен в тюрьму, а 16 февраля около 310 г. казнён вместе с 11 учениками (память 16 февраля). Тем не менее, в рассказах Евсевия упоминаются далеко не все христиане, пострадавшие в этот период, поскольку Евсевий не стремился собирать полный каталог исповедников, но лишь представил своим читателям ряд примеров мужества и твёрдости веры своих сограждан. При этом Евсевий, писавший вскоре после этих событий и лично знакомый с их очевидцами и участниками, старался умалчивать о примерах вероотступничества, слабости и малодушия, которые, конечно, тоже были многочисленными. В 311 г. император Галерий (305–314 гг.) издал эдикт, даровавший христианам право свободно исповедовать свою веру. В 313 г. этот эдикт был подтверждён Миланским эдиктом императоров Константина I Великого (323–337 гг.) и Лициния (305–323 гг.). Последние кампании преследований в 312–313 гг., при императоре Максимине Дазе (305–313 гг.), Палестину не затронули. Прекращение гонений было огромной победой христианских общин. Стойкость мучеников и преданность основной массы христиан своей вере во время гонений существенно повлияли на их положение в римском обществе, вызвали симпатии и повысили их авторитет. В 324 г. император Константин I Великий, провозгласивший себя покровителем христиан, сумел победить и отстранить от власти всех соперников, став единоличным правителем. От политики преследований Рим перешёл к политике сотрудничества с церковью. В результате административной реформы императора Диоклетиана на рубеже III и IV вв. из прежней территории Палестины и части Аравии были образованы три провинции. В Палестину Первую с центром в Кесарии была включена центральная часть территории страны с Иерусалимом, Иерихоном и Газой. Палестина Вторая с центром в Скифополе (ныне Бейт-Шеан) была сформирована из северных районов страны: Галилеи, части Самарии и Заиорданья. В Палестину Третью с центром в Петре вошли южная часть Иудейской пустыни и пространства между Мёртвым морем и заливом Акаба, населённые кочевниками. Развитие Церкви Палестины в течение последующих трёхсот лет происходило, в основном, в рамках этих административных структур. В соответствии с ними постепенно сложилась церковная организация: патриаршему престолу в Иерусалиме подчинялись митрополичьи кафедры в Кесарии, Скифополе и Петре, а им, в свою очередь, – прочие епархии. Христиане долгое время (по крайней мере, до конца IV в.) не составляли большинства населения Палестины. Помимо них здесь сохранялись значительные общины язычников, иудеев и самаритян. При этом если число язычников постепенно уменьшалось, то общины иудеев и самаритян зачастую жили закрыто, не позволяли своим членам принимать христианство и противостояли государственной политике, направленной на распространение новой веры. В силу особой значимости этого региона для самых разных традиций Палестина в эту эпоху оставалась ареной жестоких религиозных конфликтов. В ходе реформ императора Константина I Великого крупнейшие языческие храмы в главных городах, такие как храм Венеры (Астарты) в Элии, были закрыты или разрушены. Однако в сельских районах и во многих провинциальных городах старые традиции ещё долго сохранялись. Попытка императора Юлиана Отступника в 361–363 гг. пересмотреть религиозную политику империи и отказаться от поддержки христианства напрямую повлияла на ситуацию в Палестине.