Однако испанцы легко могли послать и еще большую армию. Мало того, против Хайраддина выступили и ряд местных правителей. Так, «Абу Хамму III, вторично занявший трон Абдальвадидов, шел войной на Барбароссу. Хафсидский султан Туниса собирал войска и подстрекал феодальных владетелей, даже соратников Хайраддина, на открытое выступление против крестьянской власти.
В этой ситуации Хайраддин Барбаросса решил обратиться за помощью к Османской империи. Вскоре после разгрома Уго де Монкады он созвал в Дженине наиболее видных представителей мусульманского духовенства и населения, изложил им создавшееся положение и предложил перейти под сюзеренитет Порты. Совещание согласилось с мнением Хайраддина и одобрило текст письма на имя османского султана Селима I, в котором просило принять Алжир под свое покровительство. Один из соратников Хайраддина, Хаджи Хусейн, отправился с этим письмом в Стамбул. Хайраддин тем временем сложил с себя полномочия султана и приказал читать в пятичной молитве имя Селима I.
Порта благосклонно отнеслась к предложению повстанцев и объявила о своем сюзеренитете над Алжиром. По обычаю, Селим I назначил самого Хайраддина Барбароссу первым бейлербеем Джезаир-и Гарп (Западный Алжир), прислал ему соответствующий фирман и знаки достоинства: саблю, бунчук и барабан. Одновременно было разрешено чеканить монету с именем нового сюзерена Алжира[57] и упоминать его в пятичной хутбе. Кроме того, Хайраддину были отправлены пушки, мушкеты и другое оружие, а также фирман, разрешающий ему набор добровольцев для службы в Алжире. В качестве особой милости этим добровольцам даровались права и привилегии янычарского очага. Вскоре, возможно, еще до смерти Селима I, в Алжир прибыли первые 4 тыс. муджахидов, положившие начало алжирскому очагу янычар»[58].
Так Алжир вошел в состав Оттоманской империи, хотя и сохранив широкую автономию.
Авторитет Хайраддина Барбароссы в Северной Африке существенно возрос. В 1518 г. он разбил войска испанского вассала Абу Хамму III и заставил его признать власть Османской империи, а также выплачивать дань в 10 тысяч дукатов. Однако вторжение хафсидских войск, восстание феодалов, разгром ими армии Барбароссы, измена Кара Хусейна, правившего в Шершеле, и Ахмеда ибн аль-Кади, султана Куко (Большая Кабилия), перешедшего на сторону Хафсидов, резко усложнили ситуацию. В 1519 г. Хайраддин даже был вынужден бежать из города Алжира, захваченного Ахмедом ибн аль-Кади. Барбаросса укрылся в Жижели, а затем отправился на остров Джербу. Он фактически потерял контроль сначала над восточной частью Алжира, а потом и над западной, где султан Абу Хамму III, воспользовавшись сложившейся ситуацией, прекратил выплату дани, а позже и вообще разорвал вассальные отношения с Портой.
Теперь все надо было начинать с нуля, и Хайраддин энергично принялся за дело. Его задачу существенно облегчали два момента: во-первых, внутренние беспорядки в Испании, которые на 5 лет исключили как существенный военно-политический фактор. Восстание комунерос 1520–1522 гг.[59] и его последствия вплоть до 1526 г. не позволяли Карлу V затевать какие-либо серьезные операции в Северной Африке. Во-вторых, это недовольство крестьян и горожан, которых не устраивала власть старых феодалов. Как уже говорилось, и крестьяне, и горожане ненавидели бедуинов, на которых пыталась опираться старая феодальная знать.
Поэтому, когда в 1521 г. Хайраддин Барбаросса с отрядом корсаров захватил Жижель, к нему стали стекаться тысячи сторонников со всего Алжира.
В течение четырех лет Хайраддин вернул себе контроль над Алжиром. В том же 1521 год он захватил Колло, в 1522 г. – Аннабу и Константину. Беднота везде восторженно приветствовала Барбароссу. Войска местных правителей часто переходили на его сторону. В 1525 г. Ахмед ибн аль-Кади, оказывавший упорное сопротивление, был убит собственными людьми. Большая Кабилия заявила о лояльности османам. В том же 1525 г. Хайраддин Барбаросса, не встречая сопротивления, вступил в город Алжир, где его приверженцы открыли ему ворота города. Так же легко он занял Тенесом и Шершелем. Изменник гази Кара Хусейн был выдан солдатами и казнен. Абу Хамму III, пытавшийся противостоять Барбароссе, потерпел поражение, признал сюзеренитет Порты и обязался платить дань в размере 20 тысяч дукатов, то есть в два раза больше того, что полагалось по договору 1518 г.
Вновь обосновавшись в Дженине, Хайраддин Барбаросса восстановил Диван, другие правительственные учреждения и очаг янычаров. По особо важным поводам созывались расширенные заседания «Большого дивана», на которые приглашались все видные представители мусульманского духовенства, знатные горожане, дервишские шейхи, имамы и другие представители духовенства, а также главные командиры янычарского очага.
Страна была разделена на провинции и округа во главе с беями и каидами. Для сбора налогов назначались наиболее честные и добросовестные кадии.