Валенсия практически принадлежала Альфонсо. Кодил являлся лишь номинальным королем, но большая часть территории принадлежала кастильцам, и императору оставалось лишь молвить слово, чтобы включить ее в состав империи. Сарагоса тоже казалась потерянной. Альфонсо осадил ее и поклялся захватить. На дальней оконечности полуострова один из людей Альфонсо – Гарсия Хименес – закрепился с отрядом кавалеристов, и оттуда его люди совершали постоянные набеги на Альмерию. Не была от них избавлена и Гранада, поскольку весной 1085 года кастильцы подошли к деревне Нибар, что на расстоянии лиги к востоку от Гранады, и дали бой мусульманам. Опасность была везде, и повсеместно воцарилось мрачное уныние. Мусульмане не осмеливались нападать на христиан, даже имея численное преимущество пять к одному. Отряд из четырех сотен солдат из Альмерии – избранные воины – был обращен в бегство восьмьюдесятью кастильцами. Было ясно, что, если арабы Испании будут предоставлены своей судьбе, для них возможны только две альтернативы – подчиниться императору или уехать. Многие из них выбрали второй путь. «Готовьтесь к путешествию, андалусцы, – восклицал поэт, – ибо оставаться здесь – безумие!» Тем не менее все же эмиграция была крайней мерой, и арабы не стремились к ней прибегнуть. Они считали, что еще не все потеряно и помощь может подоспеть из Африки. Там была надежда на спасение. Люди полагали, что следует обратиться к бедуинам Ифрикии, однако существовало опасение, что, высадившись в Испании, они станут грабить мусульман, а не воевать с христианами. Подумывали и об Альморавидах. Это были берберы Сахары, которые впервые играли роль на мировой исторической сцене. Они были не так давно обращены в ислам миссионером из Сиджильмасы и быстро завоевывали территории. В то время, о котором идет речь, их империя раскинулась от Сенегала до Алжира. Идея позвать на помощь Альморавидов пришлась по вкусу в основном религиозным людям. Принцы, с другой стороны, долго колебались. Некоторые из них, такие как Мутамид и Мутаваккиль, вели переписку с Юсуфом ибн Ташфином, королем Альморавидов, и неоднократно прибегали к его помощи. Но андалусские принцы в целом не испытывали симпатии к фанатичным воинам-варварам из Сахары и считали их скорее опасными противниками, чем союзниками. Однако ежедневно угрожающая смертельная опасность не оставляла выбора. Таким, по крайней мере, было мнение Мутамида, когда его старший сын, принц Рашид, указал ему на опасность допуска Альморавидов в Испанию. Тогда Мутамид ответил: «Это правда, но я не хочу остаться в истории человеком, который отдал Испанию в руки неверных; не желаю, чтобы мое имя проклинали с каждой мусульманской кафедры. По мне, так лучше быть погонщиком верблюдов в Африке, чем пастухом свиней в Кастилии».
Мутамид, таким образом, решился и предложил своим соседям, Мутаваккилю из Бадахоса и Абдуллаху из Гранады, действовать совместно и назначить послами своих кади. Абу Исхак ибн Мокана и Абу Джафар Колайи, кади Бадахоса и Гранады соответственно, прибыли в Севилью. Кади Кордовы Ибн-Адхам и визирь Абу Бакр ибн Зайдун присоединились к ним, и все четверо поднялись в Альхесирасе на борт корабля и направились к Юсуфу. Они имели полномочия пригласить его – каждый от имени своего суверена – высадиться в Испании с армией, но при этом выдвигались определенные условия, о которых записи не сохранились. Мы только знаем, что Юсуф поклялся не захватывать государства андалусских принцев. Что касается места высадки, Ибн-Зайдун предложил Гибралтар, но Юсуф предпочел Альхесирас и потребовал, чтобы этот город был отдан ему. Визирь Мутамида ответил, что не уполномочен решать такие вопросы. После этого Юсуф стал обращаться с послами холодно и давал им только уклончивые и двусмысленные ответы. Покинув его, они не могли с уверенностью сказать, что он станет делать. Он ничего не обещал, но и не отказался прибыть в Испанию.