В X–XII веках арабские путешественники отмечен оживленность его торговли. В наступивший затем период смут город, несомненно, пришел в упадок. Все же в XIV–XV веках порт посещали европейские корабли а жители города активно занимались пиратским промыслом. Приток морисков, изгнанных из Испании после падения Гранады (1492 год), увеличил его население, которое в середине XV века вряд ли превышало 20 тысяч жителей, на несколько тысяч беженцев, неимоверная озлобленность которых активизировала деятельность пиратов. И вот, чтобы предотвратить их нападения, которым подвергались главным образом испанцы, Педро Наварро направил на город пушки Пеньона. Но жители настолько страдали «от иглы, вонзившейся в сердце», что обратились за помощью к турецкому корсару Аруджу, хозяйничавшему с 1514 года в Джиджелли.

Братья Барбаросса («Рыжебородые»), которых по привычке объединяют под этим прозвищем, относящимся собственно к одному лишь Хайраддину, предстают как герои, созданные историей специально для авторов романизированных жизнеописаний. Это были четыре сына гончара из Митилены (древний Лесбос) — Арудж, Хайраддин, Элиас и Исхак, которые с юности проявляли особую склонность к пиратству. Во время одного из пиратских нападений Элиас погиб, а Аруджу, попавшему в плен, пришлось гнуть спину на галерах рыцарей ордена св. Иоанна. Неизвестно, как он освободился и по какой причине вместе с братьями покинул Архипелаг и перенес свою деятельность в западное Средиземноморье. Здесь, нападая на корабли христиан, и в особенности на испанские корабли, а также перевозя тысячи морисков в Берберию, он завоевал в 1504–1510 годах большой авторитет среди мусульман. С этого времени под его начало стали стекаться сотни авантюристов, жаждущих добычи. Хафсидский султан, заинтересованный в прибылях, предоставил ему даже право запасаться всем необходимым в его портах, а также управление островом Жельв (Джерба), который стал базой для десяти-двенадцати кораблей его эскадры.

Оказавшись в опасности, ислам обратился за помощью к этим суровым воинам. В 1512 году по призыву хафсидского наместника Арудж хотел захватить Бужи, но не смог вести штурм, так как ядром ему оторвало руку. Два года спустя он снова потерпел неудачу. Тогда он обратился к Джиджелли (1514 год), благоприятное положение которого позволяло следить за всеми перидиями борьбы между кабильскими «султанами» Бану Аббас и Куко. Своевременное вмешательство Аруджа, определившее победу Бану Аббас, обеспечило ему подкрепления и ценные советы (1516 год).

Весть о смерти Фердинанда Католика волновала тогда оккупированные испанцами порты Магриба. Жители Алжира считали, что она освобождает их от присяги, данной этому королю, но, будучи слишком слабыми, чтобы самим добиться освобождения, они торопили своего шейха Салима ат-Туми обратиться к Аруджу. Корсар тотчас же понял выгоду этой авантюры, занял сперва Шершель, находившийся во власти другого турецкого авантюриста, а затем с триумфом вошел в Алжир.

Горожане Алжира рассчитывали на быстрое избавление от Пеньона, но турецкие пушки почти не беспокоили крепость, так что население стало роптать. Вскоре саалиба, испанцы и горожане Алжира подготовили заговор с целью отделаться от корсаров. Арудж быстро пресек его, задушив шейха Салима, которого заговорщики прочили на прежнее место, и провозгласил себя султаном. Несколько казней и арестов, за которыми последовали обещания нотаблям, — и порядок был восстановлен. Алжир получил если и не спасителя, то во всяком случае повелителя (1516 год).

Уже пять лет как испанцы перестали интересоваться событиями в Магрибе, концентрируя все свои усилия в Италии против Людовика XII, и Педро Наварро, стало быть, не мог продолжать свои подвиги. Полвека испанцы боролись с турецкой опасностью, нависшей над побережьем Иберийского полуострова и их средиземноморской торговлей, посылали экспедиции в Африку, но терпели лишь одни неудачи. Первое наступление на Алжир под командованием Диего де Веры окончилось поражением (30 сентября 1516 года). Арудж воспользовался двойственным положением султана Тенеса, чтобы захватить Милиану, Медею и, наконец, сам Тенес. Тогда же жители Тлемсена обратились к нему за помощью против своего государя, который в 1511 году принял испанский сюзеренитет. Арудж незамедлительно прогнал его, Затем по-хозяйски обосновался в Мешуаре вместо претендента, которому он обещал трон. 70 зайянидов, говорят, были утоплены по его приказу. Новый государь строил крепости, покорил племя бану снассен и начал переговоры с ваттасидским султаном Феса. Его триумф однако, был кратковременным. Испанская армия, усиленная туземными контингентами, перерезала его коммуникации с Алжиром и захватила его брата Исхака, который в нарушение обязательств был убит арабами (январь 1518 года). Вышедший из Орана экспедиционный корпус в течение шести месяцев осаждал Аруджа сначала в городе, затем в Мешуаре. Оставшись в конце концов с горстью турок, однорукий пират сумел ночью бежать, но был настигнут у Рио Саладо и после отчаянного сопротивления убит вместе со своим эскортом (1518 год).

Хотя чудесная карьера этого авантюриста оборвалась в 44 года, все же, как справедливо отметил бенедиктинец Хаэдо, который в 1577–1581 годах был пленником в Алжире, Арудж «положил начало великой мощи Алжира и Берберии». С присущей ему прозорливостью он быстро понял, какую выгоду может извлечь деятельное меньшинство из соперничества между магрибскими княжествами, чтобы за их счет создать могущественное мусульманское государство, не боящееся нападений со стороны христиан. Он завоевал Митиджу, долину Шелифа, Титтери, Дахру, Уарсенис, Тлемсен и навсегда подорвал власть Зайянидов. Однако дело Аруджа было бы обречено на гибель, если бы его не продолжил и не довел в значительной мере до конца его родной брат Хайраддин.

Хайраддин, основатель Алжирского регентства. Человек, которому Арудж поручил Алжир и которого турки назначили его преемником, обладал двумя основными качествами: неукротимой волей и очень ясным политическим чутьем. Тот, кого современники прозвали Рыжебородым (Barbarossa, Aenobarbus), был подлинным основателем Алжирского регентства, а впоследствии организатором и великим адмиралом Османского флота.

Поражение брата поставило его в затруднительное положение. Жители Тенеса, Шершеля и Алжира, кабилы Куко, сторонника свергнутого государя Тлемсена, — все стремились освободиться от власти корсаров. Тогда Хайраддин принял гениальное решение и связал свою судьбу с Османской империей. Один он был бы раздавлен своими многочисленными врагами; опираясь же на поддержку Порты, он поднимал свой престиж и получал военную и финансовую помощь, которая дала бы ему возможность осуществить обширные замыслы. Поэтому он поспешил принести клятву верности султану Селиму, который дал ему титул паши и назначил эмиром эмиров (бейлербей). Более того, он получил из Константинополя 2 тысячи человек с артиллерией, затем еще 4 тысячи волонтеров, занявших привилегированное положение янычаров.

Эти подкрепления прибыли вовремя, чтобы предотвратить серьезные опасности: заговор алжирцев и племен, который был потоплен в крови, а также новый натиск испанцев под командованием Уго де Монкады, закончившийся полным провалом (1519 год). Но вследствие предательства войск Куко на