10 зуль-каады 503 года от Хиджры (31 мая (7 июня) 1110) жители Сарагосы впустили в город отряд вали Валенсии Мухаммада ибн аль-Хаджжа, что положило конец семидесятилетнему правлению бану худ в Сарагосе. Альморавиды заняли столицу последней независимой тайфы в Иберии и вступили к открытое противостояние с королём Арагона Альфонсо I, которое через несколько лет обернулось трагедией для мусульман Аль-Андалуса.
Победа альморавидов при Уклесе обозначила тактическое превосходство берберов над кастильцами, но не имела серьёзных последствий. Многие крепости, которые были уступлены королю Альфонсо VI или захвачены им, оставались в руках христиан, и берберские военачальники настаивали на продолжении войны. Когда же в июле 1109 года в Толедо умер Альфонсо VI, не оставивший после себя сыновей, стало очевидно, что более подходящего момента для похода на Кастилию может не быть. Тем более что королева Уррака, дочь Альфонсо, собиралась выйти замуж за короля Арагона Альфонсо I, что могло полностью изменить расклад сил на полуострове.
В середине мухаррама 503/августе 1109 года эмир мусульман Али ибн Юсуф пересёк море и после короткой остановки в Гранаде прибыл в Кордову. Примерно через месяц армия альморавидов двинулась на север и вторглась в пределы Кастилии, достаточно легко захватив более двух десятков крепостей, включая Гвадалахару, Мадрид и Талаверу. Последняя представляла собой хорошо укреплённый город, который Альфонсо VI захватил в 1083 году.
Согласно арабским источникам, после этого берберы осадили Толедо и три дня опустошали его окрестности, а потом вернулись в Кордову. Христианские авторы, напротив, сообщают, что альморавиды сперва осадили Толедо и в течение семи дней безуспешно пытались штурмовать город. Когда же Альваро Фаньес совершил успешную вылазку и мусульмане понесли потери, они сняли осаду и только после этого захватили Талаверу, Мадрид и Гвадалахару. Поход Али ибн Юсуфа мог обернуться ещё большим несчастьем для кастильцев, если бы не болезнь, которая распространилась в армии берберов и вынудила их вернуться обратно.
Неудачи кастильцев приободрили сарагосцев, тем более что после гибели при Уклесе графа Гарсии Ордоньеса влияние Кастилии в Риохе (соседней с Сарагосой области) значительно ослабло. В джумадаль-уля 503/декабре 1109 года эмир Ахмад аль-Мустаин с небольшим войском дошёл до города Арнедо и разграбил его (по другой версии, он двигался в сторону Памплоны и разграбил окрестности Олите). Когда сарагосцы возвращались обратно, войско кастильцев и арагонцев настигло их. Сражение произошло 1 раджаба/в конце января 1110 года, и мусульмане потерпели тяжёлое поражение. Среди погибших был и эмир Ахмад, после чего жители Сарагосы присягнули его сыну Имад ад-Дауле Абд аль-Малику с условием, что он не станет прибегать к защите христиан.
Дальнейшее развитие событий показывает, что альморавиды расценили гибель аль-Мустаина как повод для вмешательства в дела Сарагосы. Эмир Гранады Абу Мухаммад Абдаллах ибн Фатима двинулся со своим войском в сторону Сарагосы, но местные жители выехали навстречу ему с просьбой не обострять ситуацию и не вынуждать Абд аль-Малика искать поддержки у христиан. Сарагосцы хорошо знали Ибн Фатиму, потому что он во главе полуторатысячного войска пришёл на помощь эмиру Ахмаду после освобождения Валенсии. Тем не менее, когда стало ясно, что Имад ад-Дауля намеревается заключить союз с христианами, сарагосцы обратились за помощью не к Ибн Фатиме, а к вали Валенсии Мухаммаду ибн аль-Хаджжу.
Отряд альморавидов вступил в Сарагосу во второй половине 503/первой половине 1110 года. Имад ад-Дауля, опасаясь расправы, сбежал в Туделу и обратился за помощью к Альфонсо I. Король Арагона несколько лет ждал, когда ему выпадет такая возможность, и без промедления отправился в Туделу. Сражение между арагонцами и объединённым войском альморавидов и сарагосцев произошло на расстоянии двух фарсахов от Сарагосы 15 зуль-хиджжи 503/10 июля 1110 года. Мусульмане не смогли сдержать натиск противника и отступили, понеся большие потери, а среди погибших был сын Мухаммада ибн аль-Хаджжа — Яхья.
Арагонцы разбили лагерь в одном фарсахе от Сарагосы и не переставали грабить окрестности города, пока из Мурсии не прибыла армия под командованием Абдаллаха ибн Аиши. Однако напряжённость в тайфе сохранялась, потому что некоторые важные крепости по-прежнему были на стороне эмира Абд аль-Малика. Попытка овладеть крепостью Калатаюд для берберов закончилась разгромом, а их предводитель Али ибн Кунфат аль-Лемтуни попал в плен и доставлен к Имад ад-Дауле в крепость Руэда, что располагалась между Калатаюдом и Сарагосой, на правом берегу реки Халон.
Завоевание Сарагосы завершило объединение мусульманских земель Аль-Андалуса под властью альморавидов, но вместе с тем возложило на них ответственность за обеспечение безопасности долины реки Эбро. Прежде с этой обязанностью справлялись эмиры из бану худ, которые выстраивали непростые отношения с Кастилией, Арагоном, Памплоной и Барселоной, играя на противоречиях между ними.
Будучи буфером между христианским миром и остальной частью дар-уль-ислама, уже не такого сильного, но всё ещё непредсказуемого, бану худ извлекали выгоду из своего стратегического положения. Несмотря на растущее давление со стороны Арагона, они удерживали приграничные крепости Туделу, Лериду, Фрагу и Тортосу. Альморавиды нуждались в таком союзнике, и поэтому Юсуф ибн Ташфин перед смертью наказал своему сыну поддерживать эмиров Сарагосы, но случилось то, что должно было случиться и поначалу казалось очередным успехом берберов.
