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