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