часу іспанської окупації пресідіос перебували в стані облоги. Життя солдатів була вкрай важкою, так як харчувалися вони погано і нерегулярно отримували платню. Гарнізонах та містах часто загрожував голод. Несподіване виступ турків не тільки погіршило становище пресідіос, а й спричинило за собою провал іспанської політики в Африці. Ініціатива, що виходила з Алжиру, змінила весь хід африканської історії. Місто це мав достатньо скромну історію і був своєрідною самокерованої республікою. Його порт активно відвідували кораблі, а самі жителі займалися піратством. Приплив морисков з Гранади збільшив його населення до 20 тис., неймовірна озлобленість яких активізувала діяльність піратів. Щоб запобігти їх нападу, Педро Наварро направив на місто гармати Пеньон. Але жителі звернулися за допомогою до турецькому корсару Арудж, який з 1514 роки господарювали Джіджелі.
Брати Барбаросса (В«РудобородийВ»), яких за звичкою об'єднують під цим прізвиськом, належать власне лише до одного Хайраддіна, були синами тімаріота з Мітілени. У 1504-1510 роках, нападаючи на кораблі християн в Західному Середземномор'ї, а також перевозячи тисячі морисков в берберів, Арудж завоював великий авторитет серед мусульман. З цього часу під його прапори стали стікатися тисячі авантюристів, які жадали видобутку. Хафсидское султан, зацікавлений у прибутках, надав їм право запасатися всім необхідним у його портах, а також управління островом Джерба ​​(Жельв), який став базою для ескадри.
Опинившись в небезпеці, іслам звернувся за допомогою до піратів. У 1512 за призовом харсідского намісника Арудж хотів захопити Бужі, але не зміг вести штурм, оскільки був поранений. Два роки по тому він знову зазнав невдачі. У 1514 році він звернувся до Джіджеллі і отримав в 1516 році допомогу. p> Звістка про смерть Фердинанда Католика схвилювала всі порти Магрибу. Жителі Алжиру вважали, що це звільняє їх від присяги, але, будучи слабкими, вони поквапили свого шейха Садим аб-Тумі звернутися за допомогою в звільненні до Арудж. Корсар спершу зайняв порт Шершель, який перебував під владою турецького авантюриста, і з тріумфом увійшов до Алжиру. Городяни, які розраховували на швидке позбавлення від гармат Пеньон, стали проявляти неспокій. Був складений змову для того, щоб звільнитися від корсарів. Але Арудж швидко присік його, убивши шейха Селіма, і в 1516 році проголосив себе султаном.
Іспанці, зайняті європейськими справами, не могли приділяти достатньої уваги Північної Африці, і перший наступ на Алжир у вересні 1516 під командуванням Дієго де Віра закінчилося поразкою. Арудж скористався слабкістю султана Тенеса, щоб захопити Тенес, Міліану і Медес. Жителі Тлеменсена звернулися до нього за допомогою проти свого государя, який в 1511 році прийняв іспанська сюзеренітет. Арудж негайно проuнал його, потім влаштувався в Мешуаре на місці претендента, якому він обіцяв трон. Новий государ почав будувати фортеці, підкорив плем'я бану снассен і почав переговори з ваттасідскім султаном Феса. Проте його тріумф був недовгий. У 1518 році він був змушений тікати від іспанської експедиції з Алжиру, потім Мешуара, але був наздоженуть і убитий після відчайдушного опору. p> Арудж були завойовані Мітуджа, долина Шеліф, Тіттері, Дахра, Уарсеніс, Тлеменсен. Проте об'єднання розрізнених земель в єдину могутню державу було б приречене на загибель, якщо б його не продовжив рідний брат Арудж Хайраддін. Саме він став справжнім засновником Алжирського регентства, а згодом організатором і великим адміралом Османської флоту.
Поразка брата поставило його в складну ситуацію. Жителі Тенеса, ШЕРШЕЛЬ та Алжиру, кабіли Куко, прихильники поваленого государя Тлеменсена - всі прагнули звільнитися від влади корсара. Один Хайраддін був би роздавлений своїми численними ворогами. Але він звернувся за підтримкою до Османської імперії і отримав військову і фінансову допомогу. Це змусило Хайраддіна принести клятву вірності султана Селіма I, який дав йому титул паші і призначив еміром емірів (бейлербей). Більше того, він отримав зі Стамбула 2 тис. осіб з артилерією, потім ще 4 тис. добровольців, які посіли привілейоване становище яничарів.
Підкріплення прибуло вчасно, щоб потопити в крові змова алжирців і племен та відобразити в 1519 новий похід іспанців під командуванням Уго де Монкади. Але потім, внаслідок зради військ Куко на полі бою, Хайраддін був Розбитий в Кабільне хафсудской армією і змушений покинути Алжир, щоб сховатися в Джіджеллі, де повернувся до кар'єри пірата (1520-1525). p> У 1521 році, відновивши свою армію і поповнивши скарбницю, Хайраддін захопив Колло, в 1522 році - Бон і Костянтину; потім за допомогою султана з роду Бану Аббас вигнав з Алжиру кабілів Куко і зайняв в 1525 році Мітіджу. Залишалася фортеця Пеньон, загроза якої як і раніше висіла над Алжиром. Хайраддін вирішив вжити проти неї потужну атаку. Після тритижневої бомбардування 27 травня 1529 капітан фортеці Мартін де Варгас здав її.