Последний, безусловно, был уверен, что король Фердинанд Арагонский намеревался захватить Тунис, как он уже покорил Бужи и Триполи, хотя на самом деле его отвлекли от этой попытки. Поэтому он был рад принять Аруджа как капера, при условии что его действия не дадут повода для жалоб и он будет выплачивать ему одну пятую часть стоимости захваченных призов. В следующие месяцы Арудж и его брат Хайр ад-Дин, теперь присоединившийся к нему, доставили много неприятностей испанскому судоходству и спасли много тысяч испанских морисков. В качестве базы они использовали тунисский порт Голетта и, очевидно, также остров Джерба, где испанцы были разбиты в 1510 году. Братья регулярно выплачивали оговоренные суммы Хафсиду и периодически посылали богатые дары султану Селиму в Константинополь, чтобы обеспечить будущее примирение. В 1512 году Арудж совершил неудачную попытку захватить Бужи у испанцев и в сражении лишился руки. Двумя годами позже он обосновался в Джиджеле. В 1516 году население Алжира обратилось к нему с просьбой помочь изгнать испанцев с Пеньона — этой «колючки в нашем сердце». Сначала изгнав из Шершеля турецкого корсара, которому он не доверял, Арудж напал на Пеньон, но не добился успеха. Эта неудача вкупе с необоснованными требованиями и надменностью его людей подсказали жителям Алжира идею снова обратиться к испанцам. После этого Арудж казнил Салима ат-Туми и стал правителем. В сентябре того же года он отразил атаку испанцев под командованием Диего де Вера. Нападавшие понесли большие потери. Затем он выступил против шейха Тенеса, который также вел переговоры с испанцами, сверг его и посчитал территорию своей. Затем его помощь понадобилась Зайаниду, претендующему на трон Тлемсена, правитель которого подчинился испанцам в 1511 году. Изгнав правителя, Арудж не посадил претендента на трон, а навязал собственную власть. Испанский контингент, прибывший на помощь своему протеже, заставил Аруджа уйти из города. Во время отступления он был разбит и обезглавлен испанским моряком (1518), которому за это деяние было разрешено показать голову Аруджа на своем гербе.
Отправляясь из Алжира в эти экспедиции, Арудж вызвал своего брата Хайр ад-Дина из Джиджеля и назначил его своим «заместителем» в Алжире. Получив сообщение о катастрофе, Хайр ад-Дин сообщил людям, что намерен предложить Алжир и его окрестности османскому султану. Только так, заверил он, можно обеспечить их безопасность от испанских нападений, которые систематически облегчались колебаниями и неуверенностью местных правителей. Селим принял предложение, назначил Хайр ад-Дина санджак-беем (правителем региона) и отправил ему 2000 регулярных солдат и 4000 османских волонтеров. Турецкая верховная власть, вероятнее всего, вызвала местное сопротивление, подавленное Хайр ад-Дином, так же как и ранее Аруджем.
К этому времени Хафсид — правитель Туниса — осознал, что происходит. Испанская угроза уменьшилась, но стало ясно, что она сменилась османской угрозой. Поэтому он обратился к правителю Тлемсена с предложением организовать единый фронт и попытаться подкупить союзников Хайр ад-Дина в стране кабилов, что к востоку от Алжира. Между тем последний в 1519 году успешно отразил испанскую атаку под командованием Уго де Монкада. Однако вскоре после этого силы кабилов, поддержанные Хафсидом, вынудили его уйти в Джиджель, оставив Алжир кабилам, а испанский гарнизон на Пеньоне. За следующие пять лет он существенно укрепил свои позиции на востоке, захватив у Хафсидов города Бон и Константина, вытеснил кабилов из Алжира и занял равнину Митиджа за городом. В 1529 году он захватил Пеньон. Используя труд пленных, он соединил остров с материком, сформировал гавань Алжира и построил фортификационные сооружения, благодаря которым город стал главной базой османского флота на западе. В следующем году император Карл V, ставший правителем Испании, принял контрмеру — отдал Мальту рыцарям ордена Святого Иоанна, которые были изгнаны с Родоса восемью годами ранее[20].