Во второй половине X века блистательные победы византийского оружия при Никифоре Фоке и Иоанне Цимисхии над восточными арабами сделали Алеппо и Антиохию вассалами (vassal states) империи, и после этого византийская армия, возможно, вошла в Палестину. Эти военные успехи Византии имели свой отклик (repercussion) в Иерусалиме, так что в результате французский историк Л. Брейе считал возможным говорить о византийском протекторате в Святой Земле, который положил конец протекторату франкскому.
Переход Палестины во второй половине X века (969 г.) под власть египетской династии Фатимидов, по-видимому, не внес сначала какого-либо существенного изменения в благоприятное положение восточных христиан и в безопасность приезжавших паломников. Однако, в XI веке обстоятельства изменились. Из этого времени для нашего вопроса необходимо отметить два важных факта. Сумасшедший фатимидский халиф ал-Хаким, этот «египетский Нерон», открыл жестокое гонение на христиан и иудеев на всем пространстве своих владений. По его велению, в 1009 году храм Воскресения и Голгофа в Иерусалиме подверглись разрушению. В своей ярости разрушения церквей он остановился только потому, что боялся аналогичной судьбы мечетей в христианских областях.
Когда Л. Брейе писал о византийском протекторате в Святой Земле, он имел в виду утверждение арабского историка одиннадцатого века Йахйи Антиохийского. Последний рассказывает, что в 1012 году один вождь кочевников восстал против халифа, захватил Сирию и обязал христиан восстановить храм Рождества в Иерусалиме и назвал одного епископа по своему выбору патриархом Иерусалимским. Потом этот бедуин «помог этому патриарху построить заново церковь Рождества и восстановил много мест, по мере своих возможностей». Анализируя этот текст, В. Р. Розен заметил, что бедуин действовал так «возможно, с целью завоевать благорасположение греческого императора». Л. Брейе приписал гипотезу Розена тексту Йахйи. В этих условиях невозможно с такой уверенностью, как это делает Л. Брейе, утверждать истинность теории византийского протектората над Палестиной.
Однако, в любом случае, только в начале реставрации в Святой Земле, после смерти ал-Хакима в 1021 году, для христиан наступило время терпимости. Между Византией и Фатимидами был заключен мир, и византийские императоры получили возможность приступить к восстановлению храма Воскресения, постройка которого была закончена в половине XI века при императоре Константине Мономахе. Христианский квартал был обнесен крепкой стеной. Паломники после смерти ал-Хакима снова получили свободный доступ в Святую Землю, и источники за это время отмечают среди других лиц одного из наиболее знаменитых пилигримов, а именно — Роберта Диавола, герцога Нормандского, который умер в Никее в 1035 году, по пути из Иерусалима. Может быть, в это же время, то есть в тридцатых годах XI века, приезжал в Иерусалим со скандинавской дружиной, пришедшей вместе с ним с севера, и знаменитый варяг той эпохи Гаральд Гардрад, сражавшийся против мусульман в Сирии и Малой Азии. Преследования христиан вскоре возобновились. В 1056 году храм Гроба Господня был закрыт и более трехсот христиан было выслано из Иерусалима. Храм Воскресения был, очевидно, восстановлен после разрушения с надлежащим великолепием, о чем свидетельствует, например, русский паломник игумен Даниил, посетивший Палестину в первые годы XII века, т.е. в первое время существования Иерусалимского королевства, основанного в 1099 году, после первого Крестового похода. Даниил перечисляет колонны храма, говорит о выложенном мраморном поле и шести дверях и дает интересные сведения о мозаиках. У него же мы находим сообщения о многих церквах, святынях и местах Палестины, связанных с новозаветными воспоминаниями. По словам Даниила и современного ему англосаксонского паломника Зевульфа, «поганые сарацины» (т.е. арабы) были неприятны тем, что скрывались в горах и пещерах, нападали иногда с целью грабежа на проезжавших по дорогам пилигримов. «Сарацины всегда устраивали западни для христиан, прячась в горных долинах и пещерах скал, сторожа день и ночь за теми, на кого они могли напасть».
