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

1517 г., после взятия Тлемсена, оно охватывало территорию Центрального и Западного Алжира и по своим социальным и политическим основам явилось прообразом того «алжирского регентства», которое в течение 300 лет наводило ужас на всю Западную Европу.

По прибытии в Испанию новый король Карл I отправил в Алжир 10-тысячную армию под командованием дона Диего де Кордова, более известного как маркиз де Комарес. Испанский флот достиг Орана поздней осенью 1517 г. В декабре 1517 г. маркиз де Комарес перешел в наступление, его поддержали многочисленные племена бедуинов.

В январе 1518 г. у Калаа Бени Рашид в бою с бедуинами погиб брат Оруджа Ильяс. А Орудж в течение полугода отбивался от испанцев, осаждавших Тлемсен, сначала в самом городе, затем в Мешваре. В мае

1518 г., когда закончились запасы, он с отрядом всадников ночью пробрался через боевые порядки испанцев и двинулся на Айн-Темушент, а маркиз де Комарес послал за ним погоню. У завии Сиди-Муса на Рио-Саладо испанцы настигли отряд Оруджа, и в неравном бою повстанцы погибли с оружием в руках. Голову Оруджа испанцы отправили в Испанию Карлу V. Окровавленный кафтан Оруджа как драгоценный трофей долгое время хранился в Кордове в монастыре св. Иеронима.

Новым султаном Алжира с согласия всех повстанческих вождей был провозглашен брат Оруджа Хызыр Барбаросса, более известный под своим почетным именем (лякаб) Хайраддин.

Испанцы, воодушевленные успехом маркиза де Комареса, решили захватить город’Алжир. Карл V назначил командующим экспедиционным корпусом вице-короля Сицилии Уго де Монкада. 17 августа 1518 г. испанский флот в составе 38 боевых кораблей и большого количества транспортов высадил в окрестностях города Алжира восьмитысячный десант. Хайраддин Барбаросс собрал более 5 тысяч кабильских крестьян и андалусцев, занял укрепленные позиции в городе и стал ждать дальнейшего развития событий.

25 августа, в день св. Варфоломея, разразился сильнейший шторм. Испанские корабли были сорваны с якорей, волны били их друг о друга, и они «разлетались на куски, как если бы они были сделаны из хрупкого стекла», - писал испанский историк XVI века Сандоваль. Воспользовавшись ситуацией, Хайраддин двинул на испанцев, лишившихся флота, свою отборную конницу. Около 4 тысяч испанцев погибли от рук повстанцев или утонули в море, 3 тысячи Хайраддин захватил в плен. Существует предание, что Барбаросса не принял предложенные ему 120 тысяч дукатов в качестве выкупа за знатных испанских офицеров и велел казнить их.

Однако испанцы легко могли послать и еще большую армию. Мало того, против Хайраддин выступили и ряд местных правителей. Так, «Абу Хамму III, вторично занявший трон Абдальвадидов, шел войной на Барбароссу. Хафсидский султан Туниса собирал войска и подстрекал феодальных владетелей, даже соратников Хайраддина, на открытое выступление против крестьянской власти.

В этой ситуации Хайраддин Барбаросса решил обратиться за помощью к Османской империи. Вскоре после разгрома Уго де Монкады он созвал в Дженине наиболее видных представителей мусульманского духовенства и населения, изложил им создавшееся положение, и предложил перейти под сюзеренитет Порты. Совещание согласилось с мнением Хайраддина и добрило текст письма на имя османского султана Селима I, в котором просило принять Алжир под свое покровительство. Один из соратников Хайраддина, Хаджи Хусейн, отправился с этим письмом в Стамбул. Хайраддин тем временем сложил с себя полномочия султана и приказал читать в пятичной молитве имя Селима I.

Порта благосклонно отнеслась к предложению повстанцев и объявила о своем сюзеренитете над’Алжиром. По обычаю, Селим I назначил самого Хайраддина Барбароссу первым бейлербеем Джезаир-и Гарп (Западный Алжир), прислал ему соответствующий фирман и знаки достоинства: саблю, бунчук и барабан. Одновременно было разрешено чеканить монету с именем нового сюзерена Алжира и упоминать его в пятичной хутбе. Кроме того, Хайраддину были отправлены пушки, мушкеты и другое оружие, а также фирман, разрешающий ему набор добровольцев для службы в Алжире. В качестве особой милости этим добровольцам даровались права и привилегии янычарского очага. Вскоре, возможно еще до смерти Селима I, в Алжир прибыли первые 4 тыс. муджахидов, положившие начало алжирскому очагу янычар».

Так Алжир вошел в состав Оттоманской империи, хотя и сохранив широкую автономию.

Авторитет Хайраддина Барбароссы в Северной Африке существенно возрос. В 1518 г. он разбил войска испанского вассала Абу Хамму III и заставил его признать власть Османской империи, а также выплачивать дань в 10 тысяч дукатов. Однако вторжение хафсидских войск, восстание феодалов, разгром ими армии Барбароссы, измена Кара Хусейна, правившего в Шершеле, и Ахмеда ибн аль-Кади, султана Куко (Большая Кабилия), перешедшего на сторону Хафсидов, резко усложнили ситуацию. В 1519 г. Хайраддин даже был вынужден бежать из города Алжира, захваченного Ахмедом ибн аль-Кади. Барбаросса укрылся в Жижели, а затем отправился на остров Джербу. Он фактически потерял контроль сначала над восточной частью Алжира, а потом и над западной, где султан Абу Хамму III, воспользовавшись сложившейся ситуация, прекратил выплату дани, а позже и вообще разорвал вассальные отношения с Портой.

Теперь все надо было начинать с нуля, и Хайраддин энергично принялся за дело. Его задачу существенно облегчали два момента: во-первых, внутренние беспорядки в Испании, которые на 5 лет исключили как существенный военно-политический фактор. Восстание комунерос 1520-1522 гг. и его последствия вплоть до 1526 г. не позволяли Карлу V затевать какие-либо серьезные операции в Северной Африке. Во-вторых, это недовольство крестьян и горожан, которых не устраивала власть старых феодалов. Как уже говорилось, и крестьяне, и горожане ненавидели бедуинов, на которых пыталась опираться старая феодальная знать.

Поэтому, когда в 1521 г. Хайраддин Барбаросса с отрядом корсаров захватил Жижель, к нему стали стекаться тысячи сторонников со всего Алжира.

В течение четырех лет Хайраддин вернул себе контроль над’Алжиром. В том же 1521 год он захватил Колло, в 1522 г. - Аннабу и Константину. Беднота везде восторженно приветствовала Барбароссу. Войска местных правителей часто переходили на его сторону. В 1525. Ахмед ибн аль-Кади, оказывавший упорное сопротивление, был убит собственными людьми. Большая Кабилия заявила о лояльности османам. В том же 1525 году Хайраддин Барбаросса, не встречая сопротивления, вступил в