Первым делом Хименес постарался укрепить город, справедливо полагая, что мавры не позволят испанцам закрепиться в нём надолго. Понимая, что сил для продолжения завоеваний явно недостаточно, а Педро де Наварро явно враждебно относился к нему, кардинал принял решение закрепиться на завоёванных позициях и ждать ответной реакции врага.

Для сбора подкреплений и разрешения придворных дел он оставил командовать Ораном Педро де Наварро и отплыл в Испанию. Генерал, почувствовав свободу, рьяно принялся за продолжение военных действий. Собрав эскадру из 20 галер, он в конце декабря 1509 года отправился к Бужии. Этот богатый порт процветал и был хорошей добычей.

1 января 1510 года испанская армия, поддержанная флотом, высадилась на побережье возле городских укреплений и с двух сторон атаковала его. Поскольку крепостные стены были достаточно ветхими, правитель Бужии Абд-аль-Рахман предпочёл не оказывать активного сопротивления нападавшим, справедливо полагая, что лучше сберечь их для будущей борьбы. Вместе со своими приближёнными он покинул город, оставив его на милость испанской солдатни. Только благоразумие жителей Бужии, заранее покинувших свои дома, не позволило повториться оранской резне, и дело ограничилось банальным грабежом.

Дальнейшие события показали, что Абд-аль-Рахман, составляя свои жизненные планы, не учёл небольшой мелочи — своего племянника Абдаллаха, который много лет томился в подвалах городской крепости. Он оказался ключевой фигурой последующей трагедии. Его извлекли из подвалов и доставили к генералу. Понимая, что у него в руках претендент на престол, Педро де Наварро предложил ему сделку — трон в обмен на военную помощь. Абдаллах, недолго думая, согласился, поскольку престол значил для него больше, чем семейные привязанности. Именно он выдал местонахождение своего дяди и его свиты. Испанцы немедленно снарядили отряд из 500 наиболее подготовленных солдат и двинулись в горы Ночью они напали на лагерь Абд-аль-Рахмана и перебили большую часть из его пятитысячного отряда. В плен попали 1600 мавров, а в качестве трофеев испанцам достались 500 верблюдов, нагруженных, помимо всего прочего, личным имуществом убитого правителя.

Узнав о падении Бужии и гибели Абд-аль-Рахмана, правитель Алжира не стал ожидать появления под своими стенами испанской армии и добровольно признал покровительство Испании. Он безвозмездно освободил всех христианских пленников и дал согласие на постройку у входа в алжирскую гавань крепости Пеньон.

Покорив Бужию и Алжир, Педро де Наварро направился к Триполи. Этот удобный порт дано стал прибежищем пиратов, которые грабили проходившие мимо христианские суда. 25 июля 1510 года испанская эскадра появилась у входа в порт. Педро де Наварро тут же приказал высаживать войска на берег для решительной атаки города. Несмотря на попытки триполитанцев отбить десант уже на берегу, профессиональные солдаты высадились на берег и быстро двинулись к крепостным укреплениям Приступ был настолько смелым и решительным, что мавры не выдержали удара. Потеряв в бою всего 300 солдат, испанцы овладели укреплениями и ринулись грабить город. К счастью, жители Триполи уже знали о судьбе Бужии и Орана и предпочли спрятать всё самое ценное. Не получив желанных богатств, испанцы учинили в городе резню. Погибло около шести тысяч жителей.

Однако успехи испанцев были смазаны поражением экспедиционного отряда, направленного на остров Джерба. Этот оплот разбойников представлял собой безводный каменистый остров с редкими поселениями. Отряд Педро де Наварро попал в засаду во время стоянки у одного из колодцев и был вынужден отступить. Около трёх тысяч испанцев погибло, и только 600 вернулись на свои корабли. В довершение всех бед, на обратном пути к Триполи эскадра попала в страшный шторм и большая часть кораблей погибла. Сознавая, что ему не миновать королевской опалы, а возможно, и ещё более страшного наказания, Педро предпочёл перейти на службы королю Франции. Однако и здесь его настигла судьба — вскоре он попал в плен к испанцам и, чтобы не подвергнуться позорной казни, предпочёл совершить самоубийство в тюрьме.

Несколько лет соседство мавританских пиратов и испанцев носило характер мирного сосуществования. Ни та, пи другая сторона не предпринимала активных действий для того, чтобы изменить ситуацию, так продолжалось до 1514 года, когда к тунисскому султану явился Арудж, который предложил внезапно атаковать Бужию и освободить её от испанцев. Предложение было принято, и в распоряжение Аруджа были переданы ещё две галеры. С этими силами Арудж решил атаковать город. Как и следовало ожидать, атака малочисленного отряда пиратов, мало понимавших в осаде крепостей, закончилась катастрофой. Штурм был отбит, а Арудж в бою лишился руки и едва не погиб от потери крови при ампутации. Слабеющий Арудж передал командование Хайреддину и отправился зализывать раны.

Эскадра Аруджа двинулась к Минорке. Пока Арудж лежал в беспамятстве на борту флагманской галеры, Хайреддин совершил вылазку на берег и захватил испанский форт и 40 пленных. К сожалению, враждебность местных жителей не позволила ему рассчитывать на больший успех. Тогда пираты взяли курс на Корсику, у берегов которой ограбили несколько торговых кораблей.

Собрав весьма приличную добычу, эскадра вернулась в порт, где значительная часть сокровищ была передана в дар тунисскому правителю, в знак благодарности за оказанную помощь. Это вполне удовлетворило султана, и он предпочёл не вспоминать о неудаче под Бужией.

Однако о поражении хорошо помнил сам Арудж. Весной 1515 года, оправившись от ран, он начал подготовку к новой экспедиции. Ампутированную руку он заменил серебряным протезом, который благодаря искусству мусульманских механиков был очень подвижен и крайне функционален.

Собрав еще большие силы и погрузив их на двенадцать кораблей, Арудж снова отправился к Бужии. С берега его поддерживали отряды местных племён общей численностью 1500 воинов. Несмотря на противодействие испанцев, Арудж успешно высадился на берег и начал штурм Первый приступ обошёлся ему в 350 убитых и раненых, после чего пираты перешли к длительной осаде. День и ночь при помощи турецких артиллеристов мавры обстреливали из орудий крепостные укрепления. К несчастью, об осаде Бужии стало известно испанцам, и они прислали на подмогу свою эскадру. Арудж оказался запертым меж двух огней В довершение всех бед, брат Аруджа Исаак, командовавший осадной артиллерией, был разорван на куски попавшим в него испанским ядром, что, конечно, не могло способствовать повышению боеспособности осаждающих.

Понимая, что иного выхода не было, Арудж завёл свои корабли в устье реки Уэд-эль-Вебира, где посадил их на мель, а сам, с небольшим отрядом верных бойцов, ушёл в горы, рассчитывая вести против испанцев партизанскую войну.

Сколько это могло бы продолжаться — неизвестно, но одно событие весьма существенным образом изменило положение дел. 23 января 1516 года умер испанский король Фердинанд. Это возродило надежды алжирцев на избавление от испанского гнёта. Первым делом алжирцы выбрали нового правителя. Им стал шейх Селим Эйтеми. К несчастью, Селим был слишком мягким и нерешительным человеком. Поскольку своих людей для борьбы с испанцами у него явно не хватало, он решил использовать в своих интересах Аруджа и его пиратов. К нему были направлены посланцы с богатыми дарами и предложением повести армию на штурм Пеньона. Все условия для этого были. Испанское правительство было занято интригами при дворе, Хименес сильно постарел и уже не имел прежнего влияния на политику королевства. Испанцы были больше заняты внутренними делами, чем африканскими проблемами, и не могли оперативно выслать военные подкрепления на свои форпосты.