Нападение на папские галеры в самом сердце христианских владений не могло не вызвать справедливых опасений европейских монархов. Однако ещё большее впечатление это событие произвело на жителей Туниса, куда прибыл Арудж со своей добычей. Для местных жителей казалось невозможным захватить два крупных военных судна, имея лишь маленький галиот. В один момент Арудж стал лидером всех пиратов североафриканского побережья.
Помимо славы захват папских галер дал пиратам ещё и два прекрасных судна. В условиях Средиземноморья галера в хороших руках могла стать грозным оружием Понимая это, Арудж пополнил запасы и уже во главе своей небольшой эскадры продолжил крейсерство вдоль торговых путей, наводя страх и ужас на христиан.
В следующем году Арудж захватил новый приз — испанское судно с пятью сотнями солдат. Неизвестно, по какой именно причине столь ценный груз попал в руки мусульманских пиратов. Возможно, команда была слишком ослаблена цингой или другой болезнью, либо чрезмерно утомлена беспрерывным откачиванием воды из прохудившегося трюма. Как бы то ни было, в руки пиратов попали пять сотен отличных рабов, которые тут же были проданы на рынке или заняли место гребцов на галерах.
Стремясь избавиться от североафриканских разбойников, испанский король Фердинанд II задумал карательную экспедицию. Сведения об укреплениях Алжира и Орана предоставили испанцам венецианские купцы, часто посещавшие эти порты. Первым объектом нападения был выбран Оран, однако захватить этот город можно было лишь после захвата охранявшей его крепости Мерс-эль-Кебир. Именно её и сделал своей главной целью командующий испанской экспедицией дон Диего Фернандес де Кордова.
3 сентября 1505 года из Малаги вышел объединённый испанский флот и неспешно направился к берегам Северной Африки. 9 сентября он появился под стенами Мерс-эль-Кебира. Несмотря на попытки арабов помешать высадке испанцев, десант не понёс существенных потерь и без особых проблем начал обустройство осадного лагеря под стенами крепости.
Испанский штурмовой отряд быстро занял высоты, возвышавшиеся над Мерс-эль-Кебиром, и начал обстрел крепостных укреплений. Несколько раз арабская конница пыталась выбить врага с высот, однако боевые качества мавров оказались не слитком высокими и профессиональные испанские солдаты смогли отбить все атаки.
Тем не менее высокие крепостные стены и многочисленный гарнизон оставлял не слишком много шансов на успех для осаждавших. Дело решил случай. Губернатор Мерс-эль-Кебира был случайно убит ядром, и гарнизон пришёл в замешательство. В конечном итоге, посовещавшись, арабы решили сдать крепость на почётных условиях. Эта весть вызвала вздох глубокого облегчения у Диего де Кордовы. Как опытный военачальник он не мог не понимать, что с каждым днём его положение становится все более и более тяжёлым. Арабы могли практически без ограничений подтягивать резервы и готовились к нападению на испанский лагерь. В конечном итоге испанцы сами могли оказаться в роли осаждённых, без надежды на успех. Поэтому неудивительно, что де Кордова милостиво позволил гарнизону крепости выйти со всеми припасами и при оружии, дав на сборы целых три дня. При этом он следил, чтобы никто и пальцем не тронул обитателей крепости. Только один испанский солдат нарушил предписание главнокомандующего и оскорбил арабскую женщину, за что и был немедленно наказан смертью. Его расстрел происходил прямо на глазах у арабского и испанского отрядов.
