خلف "خير الدين بربروسا" أخاه "بابا عروج" فأعاد تنظيم قواته وزود أسطوله بوحدات سريعة الحركة وطلب مساعدة العثمانيين فاضطر خير الدين لإعلان التبعية للدولة العثمانية لأمور عدة منها حاجته إلى العساكر والسلاح والبارود وكثرة الأعداء من حول دفعته للبحث عن دولة قوية يعتمد عليها إزاء ذلك توجه إلى القوة العثمانية الناشئة لإعلان تبعيته لها فجهز أربع سفن محملة بالهدايا مع أربعين أسيراً وأرسلهم إلى السلطان سليم مع رسالة شرح له فيها وضعه مع أحد أتباعه وهو الحاج حسين إلى السلطان بهدف إعلامه بفتح الجزائر فقابله السلطان العثماني وقضى بتعيين خير الدين بربروسا "بكلر بك" على إقليم الجزائر بحيث أصبح إقليم الجزائر ولاية عثمانية تحت حكم خير الدين بربروسا.

وفي هذه الأثناء كان "شارل الخامس" يسعى جاهداً للتعاون مع الأمراء الحفصيين في الاستيلاء على موانئ تونس لأهميتها في السيطرة على الملاحة في البحر المتوسط فأعد حملة سنة ١٥٣٥م ضمت أربعمائة وثمانية وعشرين سفينة تمكنت من الاستيلاء على تونس وكان رد خير الدين بالإغارة على جزر البليار وأسر ستة آلاف عاد بهم إلى الجزائر ثم استرجع كورون ولبانتو وتونس وأغار على سواحل إيطاليا الجنوبية وصقلية وفي النهاية بسط النفوذ العثماني على غربي البحر المتوسط وهكذا استطاعت الدولة العثمانية خلال القرن السادس عشر، أن توحد أقاليم المغرب العربي مع أقاليم المشرق العربي.