Переселение христиан на территорию императора шло непрерывно, да и мусульмане им никак не препятствовали. По-видимому, они также не принимали последовательных мер, чтобы помешать христианам внутри и вне халифата поддерживать тесные отношения даже во времена войны. На протяжении большей части аббасидского периода византийский император был недостаточно силен и не мог сделать многого для своих единоверцев. Провал арабов у Константинополя в 718 году гарантировал, что империя продолжит существовать, но прошло два века, прежде чем Византия смогла предпринять серьезное наступление против арабов. Между тем православные Востока обрели нового чужеземного друга. Подъем империи Каролингов в VIII веке не прошел незамеченным на Востоке. Когда в конце столетия Карл Великий, которого вскоре коронуют императором в Риме, выказал особое внимание к положению дел в Святой земле, его интерес встретили с огромным одобрением. Халиф Харун ар-Рашид, который был рад найти себе союзника в борьбе с Византией, всячески поощрял его старания основывать заведения в Иеру салиме и посылать средства тамошней церкви. На какое-то время Карл заменил византийского императора в качестве монарха, чье могущество было гарантией безопасности для православных в Палестине; и они отплатили за милость тем, что прислали королю знаки своего глубокого почтения. Однако из-за упадка его империи под властью потомков и возрождения Византии участие франков было краткосрочным, и вскоре о нем уже почти ничто не напоминало, кроме разве что гостиниц для паломников, построенных Карлом, и латинских богослужений, проводившихся в храме Святой Марии Латинской, да еще латинских монахинь, служивших при храме Гроба Господня. Но на Западе об этом не забыли. В легендах и преданиях роль Карла преувеличивалась. Вскоре распространилась уверенность, что Карл учредил законный протекторат над святыми местами, а потом что будто бы он даже самолично ездил туда с паломничеством. Франкам последующих поколений право управлять Иерусалимом казалось само собой разумеющимся и законным.
Восточных христиан ближе касалось возрождение византийского могущества. В начале IX века империя пока еще находилась в обороне. Сицилия и Крит были потеряны и ото шли к мусульманам; почти каждый год арабы совершали масштабные нашествия в самое сердце Малой Азии. В середине века, в основном благодаря разумной экономической политике императрицы-регентши Феодоры, удалось реорганизовать и переоснастить византийский флот. Благодаря его силе на море Византия снова подтвердила свое владычество над Южной Италией и Далмацией. В начале X века Аббасидский халифат начал быстро деградировать. Возвышались династии на местах, главными из которых были Хамданиды Мосула и Халеба (Алеппо) и Ихшидиды Египта. Первые были прекрасными воинами и рьяными мусульманами и на какое-то время сформировали оплот против византийской агрессии. Но они не могли остановить упадка мусульманской державы. Напротив, они усугубили его, развязывая междоусобицы. В ходе этих гражданских войн Ихшидиды овладели Палестиной и Южной Сирией. Византийцы не преминули воспользоваться благоприятной ситуацией. Сначала их наступление было осторожным, но к 949 году, несмотря на доблесть хамданидского правителя Сайфа ад-Даулы, византийский военачальник Иоанн Куркуас завоевал для империи города и области в Верхней Месопотамии, которые уже три века не видели христианских войск. После 960 года, когда во главе императорской армии встал великий воитель Никифор Фока, события стали развиваться быстрее. В 961 году Никифор отвоевал Крит. В 962 году он провел кампанию на киликийской границе и взял Аназарб и Мараш (Германикею), таким образом изолировав мусульманскую Киликию. В 963 году Никифор занимался домашними делами, планируя государственный переворот, в ходе которого при помощи императрицы-регентши пришел к власти. В 964 году он вернулся на Восток. В 965 году завершил завоевание Киликии, а экспедиция, посланная на Кипр, вернула остров под полный контроль византийцев. В 966 году Никифор действовал на Среднем Евфрате, чтобы прервать сообщение между Халебом и Мосулом. Он взбудоражил весь христианский Восток, который увидел в нем своего скорейшего избавителя. Патриарх Иерусалимский Иоанн обратился к нему с призывом поспешить в Палестину. Но этот изменнический поступок в кои-то веки переполнил чашу терпения мусульман. Разъяренная толпа местных жителей схватила Иоанна и сожгла на костре.
Надежды Иоанна оказались скороспелыми. В 967 и 968 годах Никифор занимался своими северными границами. Но в 969 году он снова возглавил поход на восток, в самое сердце Сирии. Он прошел по долине Оронта, захватывая и грабя один за другим крупные города Шайзар, Хаму и Хомс, и добрался до окраин Триполи на побережье. Затем он повернул на север, оставив за собой Тортосу, Джабалу и Латакию в языках пламени, а его командиры осадили Антиохию и Халеб. Древний город Антиохия пал в октябре. Халеб сдался в конце года.