وعلى الرغم من أن تبعيّة الدويلات القائمة في مناطق شمالي إفريقيا للدولة العثمانية كانت اسمية، إلا أن تلك الحكومات تقوّت بفضل احتمائها وتبعيتها الاسمية للعثمانيين الذين كانوا أسياد الموقف الدوليّ آنذاك، وقد كانت المواجهات البحرية بين تلك الدويلات وبين الغزاة الأسبان فاتحة الطريق أمام وجود عثماني مركز في شمالي إفريقيا. وبالفعل فإن خير الدين بربروسا الذي خلف أخاه عروج اتصل بالسلطان العثماني سليم الأول وأعلن تبعيته له، فوافق السلطان العثماني على ذلك وعينه برتبة بيلزبي (بك البكوات) ، ولقبه بلقب باشا، وأرسل إليه ألفي جندي انكشاري منظم وأربعة آلاف آخرين متطوعين، ومعهم مؤن وعتاد وغير ذلك من مستلزمات. وفي عهد السطان العثماني سليمان القانوني، أقرَّ السلطان خير الدين في منصبه، وأعطاه رتبة قبطان باشا على الأسطول العثماني في البحر الأبيض المتوسط، واستدعاه إلى إسطنبول من أجل التخطيط للقيام بحملات بحرية ضد أسبانيا في عهد شارل الخامس.