W służbie sułtana W 1518 roku zginął Oruç (Baba Oruç czyli "ojciec Oruç"). Hızır przejął przydomek po zmarłym bracie, a nadto przybrał tytuł Hayreddin i zaoferował swoje usługi sułtanowi tureckiemu. Selim I Groźny nadał mu tytuł bejlerbeja (gubernatora) i wysłał do dalszej walki z Hiszpanami, udzielając mu zbrojnej pomocy. W 1519 roku Barbarossa zdobył Algier i poddał swojej zwierzchności większą część Maghrebu. W swoim państwie sprawował despotyczne rządy, jednak prowadzona przez niego polityka przyczyniła się do rozwoju gospodarczego Algieru. W latach 1521–1534 udało mu się przekształcić Algier w kwitnący ośrodek korsarski. Zbudował też potężną flotę, którą wykorzystywał w pirackich operacjach prowadzonych w interesie Turcji. W 1532 roku zaatakował Maltę. W tym też roku za swoje zasługi wojenne został mianowany kapudanem paszą (dowódcą floty tureckiej). W 1533 roku zdobył Koron i Patras, a w 1534 zajął Tunis. Jednak rok później flota cesarza Karola V dowodzona przez Andreę Dorię, zmusiła go do opuszczenia miasta.