Стремясь избавиться от североафриканских разбойников, испанский король Фердинанд II задумал карательную экспедицию. Сведения об укреплениях Алжира и Орана предоставили испанцам венецианские купцы, часто посещавшие эти порты. Первым объектом нападения был выбран Оран, однако захватить этот город можно было лишь после захвата охранявшей его крепости Мерс-эль-Кебир. Именно её и сделал своей главной целью командующий испанской экспедицией дон Диего Фернандес де Кордова.
3 сентября 1505 года из Малаги вышел объединённый испанский флот и неспешно направился к берегам Северной Африки. 9 сентября он появился под стенами Мерс-эль-Кебира. Несмотря на попытки арабов помешать высадке испанцев, десант не понёс существенных потерь и без особых проблем начал обустройство осадного лагеря под стенами крепости.
Испанский штурмовой отряд быстро занял высоты, возвышавшиеся над Мерс-эль-Кебиром, и начал обстрел крепостных укреплений. Несколько раз арабская конница пыталась выбить врага с высот, однако боевые качества мавров оказались не слитком высокими и профессиональные испанские солдаты смогли отбить все атаки.
Тем не менее высокие крепостные стены и многочисленный гарнизон оставлял не слишком много шансов на успех для осаждавших. Дело решил случай. Губернатор Мерс-эль-Кебира был случайно убит ядром, и гарнизон пришёл в замешательство. В конечном итоге, посовещавшись, арабы решили сдать крепость на почётных условиях. Эта весть вызвала вздох глубокого облегчения у Диего де Кордовы. Как опытный военачальник он не мог не понимать, что с каждым днём его положение становится все более и более тяжёлым. Арабы могли практически без ограничений подтягивать резервы и готовились к нападению на испанский лагерь. В конечном итоге испанцы сами могли оказаться в роли осаждённых, без надежды на успех. Поэтому неудивительно, что де Кордова милостиво позволил гарнизону крепости выйти со всеми припасами и при оружии, дав на сборы целых три дня. При этом он следил, чтобы никто и пальцем не тронул обитателей крепости. Только один испанский солдат нарушил предписание главнокомандующего и оскорбил арабскую женщину, за что и был немедленно наказан смертью. Его расстрел происходил прямо на глазах у арабского и испанского отрядов.
Известие об успехе экспедиции вызвало волну неподдельной радости во всей Испании и столь же неподдельного страха в Оране. Многие жители этого города поспешили собрать свои вещи и сбежали вглубь материка, справедливо рассудив, что путь в город для испанцев открыт. Однако Диего де Кордова не торопился с активными действиями. Проблема заключалась в том, что солдатам надо было платить, а денег на содержание десятитысячного войска в испанской казне не было. Сражаться же за «идею» солдаты, многие из которых вообще не были испанцами, совсем не хотели. В конечном итоге большая часть войск была отослана обратно в Испанию и с Кордовой остался лишь небольшой отряд, явно недостаточный не только для активных наступательных действий, но и для охраны завоёванных укреплений.
В конечном итоге, несмотря на успех испанской экспедиции, её конечные результаты оказались весьма спорными. Испанцы так и не выполнили своей главной задачи — не взяли Оран, а пираты лишь сменили место базирования, подыскав другие подходящие гавани. Хуже всего было то, что разбойные нападения на испанское побережье на этом не прекратились. В июле 1507 года североафриканские пираты разграбили большое селение в Андалусии. Кроме того, стало известно, что Диего де Кордова во время вылазки из крепости попал в засаду и погиб с неравном бою. Страна лишилась опытного военачальника и могла потерять все свои завоевания в Северной Африке. Первый министр короля кардинал Хименес умолял Фердинанда II снарядить новую экспедицию. Но эта идея не вызвала особого восхищения у монарха, поскольку требовала больших расходов. Только под сильным нажимом король дал согласие, и Хименес немедленно начал собирать войска и флот.
Несмотря на придворные интриги, а зачастую и открытое противодействие, Хименес 16 марта 1509 года покинул Картахену, имея в своём подчинении мощный флот в составе 80 вымпелов и множество транспортных судов. По прибытии к Орану выяснилось, что главный враг главнокомандующего располагается не на берегу, как думал Хименес, а в рядах его собственной армии. Им оказался генерал Педро де Наварро, который, втайне завидуя Хименесу, откровенно саботировал усилия своей армии. Так, он едва не сорвал утреннюю высадку армии на берег и только под угрозой ареста был вынужден выполнить указание министра.
Высадившись на берегу и совершив молебен, испанская армия двинулась дальше в направлении Орана Сломив не слишком организованное сопротивление местных жителей, испанцы бросились к городским стенам Как оказалось, гарнизон покинул город и присоединился к армии, которая ждала сражения на равнина Воспользовавшись этим, солдаты начали резню оранцев. Многие из женщин, детей и стариков, укрывшихся в мечетях, были убиты. Около четырёх тысяч жителей Орана стали жертвой кровавой резни. Вслед за резнёй начался грабёж. Испанцы получили баснословную добычу, при этом их потери составили не более тридцати человек, большинство из которых погибли во время стычек на дороге к Орану. В подземельях городской цитадели испанцы нашли около трёх сотен христианских пленников, которые тут же получили свободу. Это был, пожалуй, единственный благородный поступок испанцев при штурме Орана.
Первым делом Хименес постарался укрепить город, справедливо полагая, что мавры не позволят испанцам закрепиться в нём надолго. Понимая, что сил для продолжения завоеваний явно недостаточно, а Педро де Наварро явно враждебно относился к нему, кардинал принял решение закрепиться на завоёванных позициях и ждать ответной реакции врага.
Для сбора подкреплений и разрешения придворных дел он оставил командовать Ораном Педро де Наварро и отплыл в Испанию. Генерал, почувствовав свободу, рьяно принялся за продолжение военных действий. Собрав эскадру из 20 галер, он в конце декабря 1509 года отправился к Бужии. Этот богатый порт процветал и был хорошей добычей.
1 января 1510 года испанская армия, поддержанная флотом, высадилась на побережье возле городских укреплений и с двух сторон атаковала его. Поскольку крепостные стены были достаточно ветхими, правитель Бужии Абд-аль-Рахман предпочёл не оказывать активного сопротивления нападавшим, справедливо полагая, что лучше сберечь их для будущей борьбы. Вместе со своими приближёнными он покинул город, оставив его на милость испанской солдатни. Только благоразумие жителей Бужии, заранее покинувших свои дома, не позволило повториться оранской резне, и дело ограничилось банальным грабежом.
Дальнейшие события показали, что Абд-аль-Рахман, составляя свои жизненные планы, не учёл небольшой мелочи — своего племянника Абдаллаха, который много лет томился в подвалах городской крепости. Он оказался ключевой фигурой последующей трагедии. Его извлекли из подвалов и доставили к генералу. Понимая, что у него в руках претендент на престол, Педро де Наварро предложил ему сделку — трон в обмен на военную помощь. Абдаллах, недолго думая, согласился, поскольку престол значил для него больше, чем семейные привязанности. Именно он выдал местонахождение своего дяди и его свиты. Испанцы немедленно снарядили отряд из 500 наиболее подготовленных солдат и двинулись в горы Ночью они напали на лагерь Абд-аль-Рахмана и перебили большую часть из его пятитысячного отряда. В плен попали 1600 мавров, а в качестве трофеев испанцам достались 500 верблюдов, нагруженных, помимо всего прочего, личным имуществом убитого правителя.
Узнав о падении Бужии и гибели Абд-аль-Рахмана, правитель Алжира не стал ожидать появления под своими стенами испанской армии и добровольно признал покровительство Испании. Он безвозмездно освободил всех христианских пленников и дал согласие на постройку у входа в алжирскую гавань крепости Пеньон.
Покорив Бужию и Алжир, Педро де Наварро направился к Триполи. Этот удобный порт дано стал прибежищем пиратов, которые грабили проходившие мимо христианские суда. 25 июля 1510 года испанская эскадра появилась у входа в порт. Педро де Наварро тут же приказал высаживать войска на берег для решительной атаки города. Несмотря на попытки триполитанцев отбить десант уже на берегу, профессиональные солдаты высадились на берег и быстро двинулись к крепостным укреплениям Приступ был настолько смелым и решительным, что мавры не выдержали удара. Потеряв в бою всего 300 солдат, испанцы овладели укреплениями и ринулись грабить город. К счастью, жители Триполи уже знали о судьбе Бужии и Орана и предпочли спрятать всё самое ценное. Не получив желанных богатств, испанцы учинили в городе резню. Погибло около шести тысяч жителей.
