Еще в 899 году богатый сирийский купец Убайдаллах объявил себя живым имамом, прямым наследником Фатимы и Али (дочери Мухаммеда и ее мужа, четвертого и последнего «праведного халифа») через одного из их потомков — «шестого имама» по имени Исмаил (поэтому последователей направления ислама, основанного Фатимидами, называют также шиитами-исмаилитами). Тайные агенты-проповедники Убайдаллаха, так называемые даи, рассеялись по Аравии и Северной Африке и в конце концов захватили Йемен и обратили в ислам несколько берберских племен в Тунисе. Аббасиды пытались убить Убайдаллаха, но тот таинственно исчез. Однако через несколько лет он (или кто-то, выдававший себя за него) вновь объявился в Тунисе, назвался Махди (Избранным, Мессией), основал собственный халифат и начал завоевание новой империи, провозгласив священную миссию: низвергнуть «неверных» багдадских Аббасидов и принести искупление миру. В 973 году фатимидский халиф аль-Муизз, к тому времени уже владевший Северной Африкой, Сицилией, Египтом, Палестиной и Сирией, торжественно вступил в свою новую столицу — только что основанный город Аль-Кахира («Победоносная»), нынешний Каир.
Его преемник аль-Азис назначил Ибн Киллиса, советника своего отца, великим визирем халифата. И тот правил от имени халифа до самой своей смерти, в течение почти 20 лет. Ибн Киллис не только обладал несметными богатствами (одних рабынь у него было восемь тысяч), но был также и ученым, который вел религиозные диспуты с еврейскими мудрецами и христианскими клириками. А его карьера наглядно свидетельствует о религиозной терпимости Фатимидов (которые, с точки зрения большинства мусульман, и сами были сектантами). Эту терпимость жители Иерусалима ощутили сразу.
Евреи Иерусалима были разобщены, они жили в бедности и отчаянии, тогда как их египетские собратья при Фатимидах благоденствовали. Некоторые из них были даже личными врачами каирских халифов. При этом они были не просто придворными лекарями: ученые выходцы из торгового сословия, они стали влиятельными вельможами. Именно они, как правило, назначали нагида (князя) — главу иудейской общины фатимидской империи. Первым таким врачом-князем стал, по-видимому, Палтиель, происхождение которого не вполне ясно. Протеже Джаухара, фатимидского завоевателя Иерусалима, он сразу же постарался помочь евреям Священного города.
Ситуация в Иерусалиме, после долгих лет пренебрежения со стороны Аббасидов и ненадежного покровительства тюркских правителей, была неопределенной. Город утратил былое значение. Постоянные войны между каирским и багдадским халифом мешали паломникам приходить в Иерусалим. Время от времени случались набеги бедуинов, и иногда им даже удавалось на короткое время захватывать город. А в 974 году энергичный византийский император Иоанн Цимисхий занял Дамаск и устремился в Галилею, обещая «освободить Гроб Христа, Господа нашего, из мусульманского плена». Греки были совсем близко, и Иерусалим замер в ожидании, но Иоанн так и не дошел до города.
Фатимиды поощряли паломничество исмаилитов и шиитов в иерусалимскую Отдаленнейшую мечеть, однако суннитские пилигримы были отрезаны от города из-за войн фатимидов с Багдадом. Однако даже изоляция Иерусалима каким-то образом способствовала еще большему его прославлению: исламские авторы составляли специальные компиляции, прославляющие достоинства Иерусалима (жанр такой апологии называется фадаиль), и давали ему все новые хвалебные эпитеты: теперь город назывался не только Элия и Байт аль-Макдис, Дом Святости, но и Аль-Балат — Дворец. Но христианские паломники становились все богаче и уже превосходили числом мусульман: франки плыли морем из Европы, а из Египта каждую Пасху прибывали богатые коптские караваны.
Евреи рассчитывали на своих спасителей в Каире, где Палтиелю удалось убедить халифа дать денег обнищавшему гаону и иерусалимской