خير الدين بربروس
خير الدين بربروس باشا ، (ميلاد: 1470 في جزيرة لسبوس - وفاة: 5 يوليو 1546 في إسطنبول)، ناظر (وزير) البحرية قائد القوات البحرية والي الجزائر بربروس خير الدين باشا. اسمه الأصلي خضر بن يعقوب وعُرف باسم خضر ريس (لقب لقباطين البحر) ولَقَّّبهُ السلطان سليم الأول بخير الدين باشا، وعُرف لدى الأوروبيين ببارباروسا أي ذو اللحية الحمراء (barba: لحية، rossa: أحمر)، حيث أن الأوروبيين لقّبوا أخاه الأكبر عروج ريس بِاسم عرّوج بارباروسا بسبب لحيته الحمراء، وبعد وفاة عروج ريس، استخدموا أيضا نفس الاسم لشقيقه الأصغر خضر.
هو أحد أكبر قادة الأساطيل العثمانية إن لم يكن أشهرهم، وأحد رموز الجهاد البحري. أهم مساعديه ابناه الريسان "حسن الكبير" (بيوك حسن) و"حسن الصغير" (كوجوك حسن) كلاهما صار "باشا". شارك مع أخويه عروج وإلياس في غزوات بحرية عديدة ثم تولى منصب حاكم إيالة الجزائر ثم عينه السلطان سليمان القانوني كأول قائد عام لجميع الأساطيل البحرية للخلافة العثمانية عام 1534م فانتقل إلى إسطنبول، وعزز السيادة العثمانية في البحر الأبيض المتوسط، حتى أصبح يشار إليه "بالبحيرة التركية" من قبل بعض المؤرخين.
ذاعت شهرته بسبب فتوحاته البحرية العظيمة. وضَع نظام السياسة البحرية العثمانية ونظَام حوضِ بناء السفن العثماني "الترسانة العامرة".
توفي ودُفن في مدفنٍ خاصٍّ به يوجد حاليا في منطقة بشكطاش، بإسطنبول، ملاصق لمتحف إسطنبول البحري.
اختلف بعض المؤرخين العرب والأجانب في أصل عائلة بربروس وتعددت الأقوال في ذلك، فنسب بعضهم هذه العائلة إلى أروام جزيرة ميديلِّي وأن خير الدين وعروج أسلما لاحقاً بعد أن كانا يعملان في البحر ودخلا في خدمة السلطان أبو عبد الله محمد المتوكل الحفصي في تونس. وتشير مصادر أخرى إلى أنهم من أصل ألباني. إلا أن أغلب المصادر تشير إلى أنهم من أصل تركي، وذلك ما جاء في مذكرات خير الدين بربروس فيقول خير الدين فيها أن والده "أبو يوسف نور الله يعقوب آغا التركي" كان أحد فرسان السباهية الذين اشتركوا في فتح جزيرة ميديلي مع السلطان محمد الفاتح وبعد ذلك استقر يعقوب آغا في هذه الجزيرة واستوطن فيها وتزوج من إحدى بنات أهالي الجزيرة وقد أنجبت له أربعة أبناء (إسحاق وعروج وخضر "خير الدين" وإلياس) وبالرغم من ذكر خير الدين في مذكراته أن أمه من جزيرة ميديلي إلا أن هناك من قال أنها أندلسية، وهناك أيضاً قول أنها امرأة مسيحية من جزيرة ميديلي وأنها أرملة راهب مسيحي.
تذكر بعض المصادر أن اسم خير الدين بربروس هو "خسرف" ولا تذكر اسمه الذي ذكره بنفسه في مذكراته "خضر". وأما تسميته باسم "خير الدين" فتذكر بعض المصادر أنه بعد إنقاذه للأندلسيين اقترح عليه هؤلاء إلى جانب المغاربة على أن يغير اسمه إلى "خير الدين". يذكر أنه كُتب على الحجر الموجود في جامع خير الدين: "أمر ببناء هذا المسجد المبارك السلطان المجاهد مولانا خير الدين بن يعقوب بو ترك بتاريخ جمادي الأول من سنة ست وعشرون وتسعمائة (926هـ) المصادف نيسان 1520م." وتُذكر رواية أخرى حول تسميته بخير الدين فتقول أن السلطان العثماني سليمان القانوني سماه بهذا الاسم وقال له: "أنت من خيرة أبناء البلاد وقد سميتك خير الدين." إلا أنه المؤرخ عزيز سامح التر قال بعدم صحة هذه الرواية وأن خضر بعد احتكاكه مع العرب في شمال إفريقيا غدوا يلقبونه بخير الدين ومنذ ذلك الوقت عُرف بهذا الاسم، وقد استند في ذلك على حجر المسجد السالف ذكره بالإضافة إلى النقود المسكوكة قبل أن يلتقي بالسلطان سليمان القانوني والتي كان مكتوب عليها لقب "خير الدين" وتسميته "بالسلطان".
وقد أطلق الإفرنج تسمية "بربروس" (بالإيطالية: Barbarossa) على الأخوين عروج وخير الدين وتعني هذه الكلمة «ذوي اللحى الحمراء» أو "الشقراء" أو "الصهباء" أو "الزعراء" وتكتب بعدة طرق منها (بربروس - بربروسا - باربروس - باربروسا) ونُقلت إلى اللغة العربية بحرفيتها، وبقيت سائرة حتى كادت تطغى على الأسماء الأصلية للأخوين.
تنص بعض المصادر العربية على مولد خير الدين في سنة 871هـ الموافقة لسنة 1466م، بينما تنص بعض المصادر الأجنبية على أن ولادته كانت في سنة 1466م، أو في 1478م. والده هو "أبو يوسف نور الله يعقوب آغا التركي" أحد فرسان السباهية الذين استوطنوا جزيرة ميديلي بعد فتحها على يد السلطان محمد الفاتح، وبعد استقراره في الجزيرة تزوج إحدى بنات أهالي الجزيرة التي أنجبت له أربعة أبناء وهم: إسحاق ثم عروج ثم خضر خير الدين ثم إلياس. ويذكر المؤرخون أن خير الدين وأخوته نشأوا في جزيرة ميديلي نشأة إسلامية صلبة، فاتجه أحد أخوته اتجه للعلم ودراسة القرآن الكريم والفقه، فتذكر بعض المصادر أنه أخوه الأكبر "إسحاق"، وتذكر أخرى أنه "إلياس". ويذكر خير الدين في مذكراته أنه أخاه "إسحاق" مقيمًا في قلعة ميديلي وكان هو وعروج مولعين بركوب البحر، وعلى أثر ذلك اقتنى عروج سفينة للتجارة، بينما اتخذ خير الدين مركبًا ذا ثمانية عشر مقعدًا. وأخذ الأخوة يعملون في التجارة فيتنقلون بين "سلانيك" و"أغريبوز" يجلبون منهما البضاعة ويبيعونها في ميديلي.
عمل خير الدين إلى جانب إخوته في بداية حياته في التجارة وكانوا يتنقلون بين جزر بحر إيجة يجلبون من هذه الجزر البضائع ويبيعونها في مسقط رأسهم ميديلي، إلا أن أخاه الأكبر عروج أراد أن يتوسع في نشاطه فتوجه إلى طرابلس الشام بجانب أخيه إلياس، وفي طريقه إليها صادف فرسان جزيرة رودس واشتبك معهم في معركة كبيرة قُتل على أثرها إلياس ووقع عروج في الأسر فنُقل إلى جزيرة رودس وسجن فيها. وبعدما سمع خير الدين بوقوع أخيه في الأسر اتجه من ميديلي إلى مدينة بودروم بجانب صديق له يدعى "غريغو" الذي كانت له علاقات في جزيرة رودس فدفع له المال لكي يفدي أخاه، إلا أنه غريغو احتال على خير الدين وأخبر فرسان الجزيرة بأنه موجود في بودروم وأخبرهم باستعداده لإنقاذ عروج، ففشلت مساعي خير الدين في إنقاذ أخيه، وتعنت فرسان رودس عندما علموا بخبرته في البحر وغِناه وأن أخاه خير الدين يحاول من مدينة بودروم إطلاق سراحه، فاستمروا في تعذيبه وزيادة الحراسة عليه. وبعد مدة نُقل من السجن ليعمل في التجديف في إحدى السفن المتوجهة إلى مدينة أنطاليا، وقد كان في واليها في تلك الفترة الأمير العثماني شهزاده قورقود بن بايزيد الثاني وقد تعود بأن يفدي (يعتق) في كل سنة مائة أسير تركي، وصودف أن عروج كان جدافًا في السفينة التي تنقل الأسرى ونظرًا لقيمته لم يجعله الرودسيين ضمن قائمة المائة أسير الذين سيتم الإفراج عنهم، وتمكن بعد ذلك عروج من فك قيوده والهرب من الأسر، واستطاع الوصول إلى الساحل واستقر في قرية تركية لمدة عشرة أيام، انتقل منها بعد ذلك إلى متجهًا إلى ميديلي، وفي طريقه إليها بلغ مدينة أنطاليا فلقي فيها رجلًا يدعى "علي ريس" يمتلك سفينة يتاجر بها بين أنطاليا والإسكندرية وقد بلغته شهرة عروج فرحب به وعمل معه ثم لم يلبث عروج حتى أصبح قبطاناً ثانيًا للسفينة. وفي هذه الأثناء كان خير الدين قد يئِس من الانتظار في بودروم فقفل راجعًا إلى ميديلي. وعند وصول عروج إلى الإسكندرية قام بإرسال رسالة إلى عائلته في ميديلي ليخبرهم بنجاته من الأسر. ويحتمل أن تكون سنة خلاص عروج من الأسر في سنة 911هـ الموافقة لسنة 1506م.
استمر عروج بعد أن نال حريته في العمل في البحر الأبيض المتوسط وذهب إلى الإسكندرية واستقر مدة فيها، وعندما كان هناك استدعاه السلطان المملوكي قنصوه الغوري للمثول بين يديه، وكلفه بقيادة أسطوله، فوافق عروج على ذلك، وذهب إلى ميناء بياس بخليج الإسكندرون لجلب الأخشاب الكافية لصناعة الأسطول على أن يتجه بعد ذلك إلى مصر، إلا أن فرسان جزيرة رودس علموا بذلك وقاموا بالإغارة على سفنه وأحرقوها، فسحب عروج جنوده إلى البر وصرفهم إلى بلدانهم، وتوجه هو إلى أنطاليا وأمر هناك بصناعة سفينة أغار بها على سواحل رودس، وعاد بعد ذلك إلى أنطاليا بعد أن نجى من هجوم آخر قام به فرسان رودس استولوا فيه على سفينته الخاصة وأحرقوا سفن بحارته. توجه عروج لاحقًا إلى مانيسا والتقى بالأمير العثماني قورقود بن بايزيد الثاني الذي أَهداهُ سفينتين حربيتين ووصاه بأن يذهب إلى غرب البحر الأبيض المتوسط لكي ينظر في أوضاع المسلمين الذين يقتلون من قبل الإسبان في الأندلس، وخرج بعد ذلك وخاض عدد من المعارك البحرية واستولى على عدد من السفن والغنائم، ورجع بها إلى ميديلي فكان في استقباله في الميناء أخويه إسحاق وخير الدين. وفي هذه الأثناء وصل خبر اعتلاء سليم الأول عرش الدولة العثمانية ومعاداته لأخيه قورقود الذي كان مقربًا من البحارة العثمانيين وبالخاصة عروج الذين كانت سفينته هدية من قورقود فخرج عروج على أثر ذلك وتوجه إلى الإسكندرية وكان ذلك تقريبًا في سنة 918هـ الموافقة لسنة 1513م.
في سنة 918هـ الموافقة لسنة 1513م توجه عروج من ميديلي إلى الإسكندرية وفي طريقه استولى في سواحل جزيرة كربة على سبع سفن، وقد كان محرجًا من السلطان قنصوه الغوري بسبب فقدانه للسفن التي منحها له فقام على أثر ذلك بإهداء جزء من الغنائم له التي غنمها في طريقه إليه. وفي ربيع سنة 1513م استأذن عروج من السلطان قنصوه الغوري في الخروج إلى الغزو فأذن له بذلك، فتوجه إلى إلى سواحل قبرص ومن هناك توجه نحو الغرب فوصل إلى جزيرة جربة بتونس. وبعد اعتلاء سليم الأول عرش الدولة العثمانية أصدر أمرًا بمنع الإبحار في شواطئ الأناضول وموانئها، وللتأكد من تنفيذ أمره عين قبطانًا يدعى "إسكندر باشا" الذي كان يضايق البحارة بدعوى أنهم من رجال الأمير قورقود -الذي كان مقربًا من البحارة العثمانيين- ولم يكن يسمح لهم بركوب البحر، وعندما بلغت أخباره لخير الدين قرر مغادرة ميديلي فشحن سفنه بالقمح ثم مضى بسرعة إلى طرابلس الشام حيث استبدل القمح بالشعير ثم ذهب إلى بروزة ثم توجه إلى جزيرة "أياموري" المقابلة لبروزة واشترى هناك سفينة أعجبته. ومن هناك اتجه إلى أخيه عروج في جزيرة جربة بتونس.
بينما كان الإخوة في جزيرة جربة اتفقوا على الاتجاه إلى تونس بنية الجهاد، ويذكر خير الدين في مذكراته أنهم قالوا قبل التوجه إليها: "ما دام الموت نهاية كل حي فليكن في سبيل الله". فدخل الأخوة عروج وخير الدين بالإضافة إلى "يحيى ريس" على سلطان تونس الحفصي أبو عبد الله محمد المتوكل وقالوا له: فوافق السلطان على ذلك ورحب بهم. أذن السلطان للبحارة الأتراك بالرسو في ميناء حلق الوادي فعملوا على تقوية مركزهم وحصنوه بشكل جيد، وأدركوا أهمية تونس وأهمية موقعها، وقد كان ميناء حلق الوادي متحكمًا في خليج تونس. قضى البحارة شتاء ذلك العام (1513م-1514م) هناك وعند حلول الربيع بدأوا بغزواتهم البحرية حتى بلغوا جزيرة سردينيا وهناك استولوا على سفينة أحد القراصنة كان فيها مائة وخمسون أسيراً. واستولوا على سفينة كبيرة أخرى كانت محملة بالقمح، وقد وجدوا القراصنة الموجودون عليها قد هربوا ولاذوا بالفرار على قواربهم، وفي الصباح التالي استولوا أيضاً على سفينتين أخريين إحداهما مشحونة بالعسل والزيتون والجبن، والأخرى سفينة جنوية كانت محملة بالحديد ثم رجعوا إلى تونس. كذلك تذكر بعض المراجع أن الإخوة بربروس استولوا على سفينتين تابعتين للبابا يوليوس الثاني بين كورسيكا وإلبا وقد كانت هاتين السفينتين عملاقتان بالمقارنة بسفن الإخوة بربروس (ربما تكون هذه الغزوة هي إحدى الغزوات السابقة) وبعد هذه الحادثة ذاع صيت عروج في كامل أوروبا.
هناك عدة عوامل داخلية وخارجية ساعدت الأخوين عروج وخير الدين في فتح جيجل ثم الجزائر بالكامل، فمن العوامل الداخلية في النصف الشرقي للجزائر ضعف وانحلال الدولة الحفصية التي كانت تحكم ذلك النصف، أما في النصف الغربي الذي كانت تحكمه الدولة الزيانية انتشار الظلم واللصوصية والمجاعات والأوبئة التي أرغمت الناس على على مغادرة منازلهم وأوطانهم. أما العوامل الخارجية فأولها سقوط الأندلس سنة 711هـ/1492م، وقيام الدول الأوروبية باحتلال أجزاء كبيرة من المدن الإسلامية الساحلية الواقعة في المنطقة الجنوبية للبحر الأبيض المتوسط خوفًا من عودة المسلمين الذين كانوا يحكمون الأندلس لستة قرون. ففي ظرف خمس سنوات (من سنة 910هـ/1505م إلى سنة 915هـ/1510م) بالنسبة للجزائر فقط احتلوا "المرسى الكبير" و"وهران" و"أرزيو" و"مستغانم" و"شرشال" و"الجزائر" و"بجاية" و"عنابة" وأصبحوا يتدخلون في الشؤون الداخلية لبقايا تلك الدول والإمارات.
حسب مذكرات خير الدين فإن الإخوة بربروس أمضوا شتاء العام التالي (918هـ/1513م تقريبًا) في تونس وعند حلول ربيع العام التالي 919هـ/1514م خرجوا للغزو وخلال ثلاثة عشر يومًا وصلوا إلى ميناء نابولي فصادفوا مركبًا كبيرًا متوجهًا إلى إسبانيا كان فيه ما بين ثلاثمائة إلى أربعمائة مقاتل فشرع البحارة في مهاجمته ووقعت بينهم معركة كبيرة تمكنوا على إثرها بالاستيلاء عليه، إلا أنهم تعرضوا لخسائر كبيرة فقد مات في هذه المعركة مائة وخمسون وجرح ستة وثمانون من البحارة. وتبين لهم أن السفينة كانت تحمل على متنها خمسمائة وخمسة وعشرون شخصًا، أسروا منهم مائة وثلاثة وثمانون، وأما الآخرون فقد تم قتلهم وقد كان من بين القتلى وال لإحدى المقاطعات الإسبانية الكبيرة. بعد ذلك استولوا على سفينة أخرى ورجعوا بها إلى تونس حيث تمت معالجة عروج الذي جرح في إحدى هذه المعارك.
جعلت هذه المعركة الأخيرة اسم الإخوة بربروس وبالأخص عروج ينتشر بشكل كبير، فأعد الإسبان عشر سفن من نوع قادرغة بهدف إلقاء القبض عليهم، لكن البحارة كانوا قد خرجوا متجهين إلى جنوة، إلا أنه بسبب مخالفة الرياح توجهوا إلى سواحل الجزائر ورسوا أمام "قلعة بجاية". وأما السفن الإسبانية فإنها عندما لم تجد البحارة في جنوة توجهت إلى بجاية (كانت بجاية محتلة من الإسبان في ذلك الوقت)، كان الاشتباك مع الإسبان على الساحل فيه خطورة كبيرة لذلك انطلق الأخوة بربروس مبتعدين عن الساحل، فظنت السفن الإسبانية أنهم قد هربوا فقاموا بملاحقتهم، وعندما ابتعدوا عن الساحل بشكل كافي أمر عروج بالعودة والاقتراب من السفن الإسبانية، فدهشوا بهذه المناورة. جرت بينهم معركة حيث قاموا خلالها بهجوم خاطف تمكنوا فيه من الاستيلاء على سفينة القيادة مع ثلاثة سفن أخرى. فلاذت باقي السفن بالهرب نحو بجاية محتمين بقلعتها.
اختلفت آراء الإخوة عروج وخير الدين فقد كان الأول يريد أن يهاجم القلعة ليستولي على السفن بينما أراد خير الدين الرجوع إلى تونس والاكتفاء بالأربعة السفن التي أخذوها. لم يأخذ عروج برأي أخيه بل أعطى أوامره بالهجوم على قلعة بجاية التي كانت تعج بالجنود الإسبان فضلًا عن الجنود الذين التحقوا بهم من السفن الست. شرع عروج في مهاجمة القلعة التي كانت تطلق وابلًا من قذائف المدفعية والقنابل، وخلال ذلك فقد البحارة الأتراك ستين من رفاقهم وأصيب عدد كبير، وعندما كانوا على وشك الاستيلاء على القلعة أصيب عروج بقذيفة في ذراعه اليسرى، وعندما رأى الإسبان ذلك فتحوا أبواب القلعة وقاموا بمهاجمة البحارة، وبعد أن رأى خير الدين إصابة أخيه حنق عليهم فقام بهجوم عنيف على الجنود مع ثلاثمائة أو أربعمائة من رجاله، وتمادوا في تعقبهم حتى وصلوا أبواب القلعة وقتلوا خلال هذا الهجوم ثلاثمائة أسباني وأسروا مائة وخمسين. ونظرًا لإصابة عروج البليغة الذي كان قد فقد وعيه اضطر البحارة للانسحاب، وتمكنوا من الرجوع إلى تونس بأربعة عشر سفينة. وبعد رجوعهم قام الجراحون بتنظيف جراح عروج إلا أن آلامه كانت تتضاعف ولهذا السبب اجتمع الجراحون على قرار قطع ذراعه.
تذكر بعض المراجع العربية هذه المناوشة بروايات مختلفة عن التي ذكرها خير الدين في مذكراته والتي سلف ذكرها. فتقول إحدى هذه الروايات أن أحد أعيان بجاية طلب من الإخوة بربروس تحرير بجاية من السيطرة الإسبانية، فلبى عروج طلبه وخرج إليها على أربعة سفن وعلى ظهرها حوالي مائة مقاتل، ووجد ثلاثة آلاف مقاتل ينتظرونه في شرق المدينة، فباشروا الهجوم وحاصروا المدينة حوالي ثمانية أيام، وفي اليوم التاسع احتلوا الميناء، ولكن قذيفة سقطت على يد عروج اليسرى فجرحته جرحًا بليغًا، فأسرع رفاقه ونقلوه إلى السفينة ونقلوه إلى تونس، وبالرغم من المداواة التي تلقاها عروج إلا أن الأطباء قرروا قطع ذراعه. وتوجد رواية أخرى تقول أن الملك "أبو بكر الحفصي" من قسنطينة أرسل لهما العلماء والأعيان من بجاية يستصرخون لإنقاذها من يد الإسبان، فلبى عروج وخير الدين هذا النداء بعد أن تشاورا مع رجالهم، فاتفقوا مع جماعات المجاهدين حوالي بجاية ورجال القبائل بقدومهم، فاتقفوا على ساعة معينة يجتمعون بها عند أسوار بجاية. توجه عروج بقيادة ثلاثة آلاف مقاتل إلى بجاية، وعند وصوله إليها وجد خمسة عشر سفينة إسبانية قدمت للتو من إسبانيا راسية بمرسى بجاية فاعترضت أسطول الإخوة بربروس، ولم يكن باستطاعتهم مهاجمتهم نظرًا لتفوقهم في العدد والعدة، فقام البحارة الأتراك بحيلة فتظاهروا بالانسحاب فرارًا من الأسطول الإسباني، فقام الأسطول الإسباني بتتبعهم إلى أن أصبح تحت مرمى مدافع البحارة المسلمين، فقاموا بمراوغة بحرية استطاعوا فيها الاستيلاء على أحد السفن الإسبانية، وقاموا بإغراق إحدى السفن، وانهزمت باقي السفن على كثرتها. وهنا اختلف الإخوة عروج وخير الدين فقد كان الأخير يرى وجوب محاصرة المدينة بحرًا، وقطع كل مدد عنها إلى أن تستسلم، بينما كان عروج يرى وجوب النزول إلى البر ومهاجمة المدينة من جهة، بينما يهاجمها مجاهدوا أهل البلاد من الجهة المقابلة، وقد كان عروج هو القائد فتم الأخذ برأيه. وهكذا نزل عروج بسفنه بصحبة خمسين رجلًا من رجاله الأتراك يستطلعون أسوار المدينة وحصونها، وقد كان الإسبان في نفس الوقت ينظرون لهم من الشرفات، إلى أن أصبحوا على مرمى بنادق المدافعين، فانهالت عليهم طلقات الإسبان، وأصابت ذراع عروج رصاصة بندقية فكسرتها، فاضطر إلى الرجوع إلى تونس لمعالجة جرحه، ولم يجد الأطباء من علاج إلى بترها.
في شتاء ذلك العام استعاد عروج عافيته، وعند حلول ربيع سنة 920هـ/1515م تقريبًا خرج البحارة بقيادة الإخوة بربروس إلى سواحل الأندلس في ثمانية مراكب ويقول خير الدين في مذكراته يصف وضع المسلمين في الأندلس بعد سقوطها: ""كانت المدينة الإسلامية غرناطة قد سقطت قريبًا بيد الإسبان. كان الإسبان يقومون بمظالم كبيرة في حق المسلمين الذين كان الكثير منهم يعبدون الله في مساجد سرية قاموا ببنائها تحت الأرض. لقد دمر الإسبان وأحرقوا جميع المساجد وصاروا كلما عثروا على مسلم صائم أو قائم ألا وعرّضوه وأولاده للعذاب أو الإحراق."" خلال ذلك قام الإخوة بحمل عدد كبير من المسلمين الأندلسيين في السفن ونقلهم إلى الجزائر وتونس. وعندما كانوا في سواحل المرية لاحت لهم سبعة سفن استطاعوا الاستيلاء على واحدة منها وقد كانت سفينة هولندية محملة ببضائع جلبت من الهند ولم يستطيعوا اللحاق بباقي السفن لمخالفة الريح. ثم توغلوا في جزيرة منورقة بعد مضي خمسين أو ستين يومًا على خروجهم من تونس فصادفوا مائتي مقاتل مدججين بالسلاح قتلوا منهم سبعين أو ثمانين واستولوا على خمسة أو ستة قطعان من الأغنام، وقد كان هؤلاء المقاتلين قد خرجوا لمهاجمة البحارة من البر بينما خرجت عشرة سفن إسبانية لمهاجمتهم من البر عندما علموا أن الإخوة بربروس قد رسوا في ميناء منورقة، وعندما علم خير الدين بذلك فرق الأسرى على السفن ثم انطلقوا من منورقة متجهين إلى جنوة، فاستولوا على أربعة مراكب في طريقهم، وقد كان من أثر هذه الحملات أن شاع اسم بربروس في جميع أنحاء أوروبا وأصبحوا أسطورة في نظرهم. أغاروا أخيرًا على جزيرة كورسيكا ثم توجهوا إلى ميديلي.
توجه الإخوة بربروس إلى مسقط رأسهم جزيرة ميديلي وقد كانوا يريدون أن يقضوا شتاء ذلك العام بين أهلهم وأقاربهم، وخلال تواجدهم هناك يذكر خير الدين في مذكراته أن عروج قال: وانفق عروج وخير الدين كل أموالهم التي غنموها في الجزيرة وعلى تجهيز سفنهم. وعند حلول الشتاء أذن خير الدين لبحارته بقضاء ذلك الفصل بين أهليهم ممن كانوا يقيمون قريبًا في الأناضول والروملي. وعند اقتراب فصل الربيع بدأت أفواج الشباب الذين بلغتهم شهرة الإخوة بربروس تتوافد إلى الجزيرة للعمل معهم كبحارة، فانطلقوا تاركين ميديلي في عشرة مراكب بحرية وفي طريقهم استولوا على خمسة عشر أو ستة عشر قطعة بحرية استولوا على الجيد منها وأغرقوا التالف منها، وقد خمس من السفن الي غنموها محملة بزيت الزيتون وواحدة منها محملة بالعاج، وأما بقية السفن فقد كانت محملة بالأموال وبضائع مختلفة، وبلغ مجموع الأسرى أكثر من أربعمائة امرأة وعددًا كبيرًا من الرجال. وفي اليوم التاسع والعشرين على مغادرتهم ميديلي دخلوا ميناء حلق الوادي بتونس، فقاموا ببيع غنائمهم هناك وأعطوا السلطان حصته وقد رحب بهم واستقبلهم في قصره، وقد أهدى للأخوين عروج وخير الدين خيولًا فارهة مجهزة وكافأ كلًا منهم بحلة من الفراء وأكرم من معهم من البحارة.
أمضى الإخوة بربروس الشتاء في تونس وعند حلول الربيع خرجوا في اثني عشر مركبًا فأغاروا على إحدى القلاع بجزيرة صقلية وأسروا ما يقرب من ثلاثمائة أسير قاموا بتوزيعهم على المراكب كمجدفين، كما استولى أحد البحارة واسمه "دلي محمد ريس" على إحدى السفن التجارية التي كانت محملة بالسكر. وفي اليوم التالي استولوا على أربعة مراكب اثنتان منهما محملتان بالجوخ، وإحداها مشحونة بأعمدة شراعية، وأما الرابعة فقد كانت محملة بالبارود، ورجعوا إلى تونس بعد مرور ثلاثة وثلاثين يومًا.
كان خروج الأخوين عروج وخير الدين من الأراضي العثمانية وتركهم لمسقط رأسهم ميديلي بعد اعتلاء سليم خان عرش الدولة العثمانية، فقد كان عروج مقربًا من الأمير قورقود الذي قام أخوه سليم بمعاداته بعدما اعتلى العرش وقتله، وأما خير الدين فقد لحق أخاه عروج إلى تونس خشية من السلطان سليم. بعد استقرار عروج وخير الدين في تونس طوال هذه المدة وازدياد شهرتهما وقوتهما لم يعودا يخشيان السلطان سليم فقد أدركا سياسته الإسلامية، وعلى هذا أرادا تطوير علاقتهما به، فتم إرسال "محيي الدين بيري ريس" إلى إسطنبول عاصمة الدولة العثمانية وأرسلوا معه عدد من الهدايا ورسالة كتبها خير الدين. غادر بيري ريس تونس في ست قطع بحرية فوصل إلى إسطنبول في اليوم الحادي والعشرين من خروجه، واستقبله السلطان سليم الأول في محرم 922هـ الموافق مارس 1516م، وقرأ السلطان سليم رسالة خير الدين وبعد قراءته للرسالة يُذكر أنه رفع يده للدعاء فقال: «اللهم بيض وجهي عبديك عروج وخير الدين في الدنيا والآخرة، اللهم سدد رميتهما واخذل أعداءهما وانصرهما في البر والبحر». ولقي بيري ريس حفاوة كبيرة من السلطان، وأرسل معه إلى تونس سفينتين حربيتين مليئتان بالمعدات الحربية والقذائف إحداهما لعروج والأخرى لخير الدين، وأرسل أيضًا سيفين قد حُليت قبضتهما بالألماس وخلعتين سلطانيتين ونيشانين وخرج بيري ريس إلى تونس. في الوقت الذي كان فيه بيري ريس في إسطنبول خرج عروج وخير الدين إلى مضيق جبل طارق على أن يذهبوا من هناك إلى الأندلس لإنقاذ المزيد من المسلمين هناك.
وصل بيري ريس إلى تونس وقد كان يحمل رسالة أرسلها السلطان سليم الأول إلى السلطان الحفصي محمد المتوكل قال فيها: واجتمع أشراف تونس في حفل كبير قام فيه بيري ريس بتقليد خير الدين سيف السلطان سليم وألبسه الحلة التي أرسلها له. يذكر خير الدين في مذكراته أن سلطان تونس بعدما رأى حفاوة السلطان سليم الأول للأخوين بربروس تغيرت معاملته لهما، وقال لخير الدين: "إن طريقك وطريق أخيك عروج سينتهي إلى القيادة العامة لبحرية الدولة العثمانية، فهنيئًا لكما بذلك." ومنذ هذه اللحظة تغير موقف سلطان تونس من الأخوين وتحفظ عليهما خوفًا منه أن يأخذا مملكته لصالح العثمانيين.
يذكر خير الدين في مذكراته أنهم انسحبوا بعد مناوشة بجاية الثانية إلى مدينة جيجل لكي يترصدوا للسفن التي قدمت لمساعدة الإسبان الموجودين في قلعة بجاية. إلا أنه لا يذكر أي معركة قامت بينهم وبين الجنود المتواجدين في جيجل التي كانت تحت حكم جنود جمهورية جنوة. بينما تذكر أكثر المراجع الأخرى معركة دارت بين البحارة الأتراك وجنود جمهورية جنوة. تختلف المراجع القديمة والحديثة في تاريخ دخول الإخوة بربروس إلى مدينة جيجل فبعضها يحدده بسنة 918هـ/1513م وبعضها بسنة 919هـ/1514م والبعض الآخر بسنة 920هـ/1515م، وكذلك حددها البعض بسنة 921هـ/1516م، وسبب الاختلاف في التواريخ يعود للخلط بين المحاولات الفاشلة للإخوة بربروس في تحرير بجاية. ويرجح أكثر المؤرخين أن دخول الإخوة بربروس لجيجل كان في سنة 919هـ/1514م.
بعد انسحاب الإخوة بربروس ببحارتهم من مدينة بجاية توجها إلى مدينة جيجل التي وجدا فيها ضالتهما المنشودة، فقد كانت محتلة من قبل دولة أجنبية مسيحية، وقريبة من مدينة بجاية وصالحة لأن تكون منطقة إسناد عندما يحاولان الهجوم على بجاية مرة أخرى. ورأوا أن حصار بجاية ليس بالأمر الهين، وأن وجودهم في تونس يبعدهم عن أرض المعركة القادمة، فصمموا على فتح جيجل التي كانت فيها حامية لصالح جمهورية جنوة، فقاموا باتصالات سرية مكثفة مع أهالي جيجل والقبائل المحيطة بها، وبعد الاستعدادات باشر الإخوة بربروس برجالهم الهجوم على حامية جنوة، وبعد مقاومة بسيطة تمكنوا من فتح المدينة واستسلم جنود الحامية الجنوية. وتم للبحارة الأتراك فتح مدينة إسلامية من يد الأوروبيين، وكانت أول مدينة يفتحونها على ساحل البلاد.
يذكر خير الدين في مذكراته أن وفدًا وصل من مدينة بجاية الجزائرية يطلب من الأخوين عروج وخير الدين أن يقوموا بتحرير مدينتهم من السيطرة الإسبانية، وكان الوفد يحمل رسالةً جاء فيها: وعلى أثر هذه الرسالة توجه الأخوين عروج وخير الدين إلى بجاية يريدان تحريرها. وفي طريقهم إليها استولوا على سفينة محملة بالشمع وعليها أربعون أسيراً من الأندلسيين فقاموا بتحريرهم جميعاً وأرسلوهم إلى تونس مع "دلي محمد ريس". وصلوا إلى بجاية ومعهم ألفين وثلاثة وثلاثين بحارًا، وعشرة سفن، ومائة وخمسين مدفعاً، وآلاف من الأسرى الذين يقومون بالتجديف. واشتبكوا مع الإسبان في معركة دامت ثلاث ساعات ونصف، قتل فيها أكثر الإسبان، ولحق بالبحارة عشرون ألف من أعراب البوادي. تحصنت بقلعة بجاية شرذمة من الإسبان المتبقين واستمروا في المقاومة مدة تسعة وعشرين يومًا. وحال عدم امتلاك البحارة الأتراك للمدافع التي تستخدم في قصف الحصون دون استيلائهم على القلعة وفتح ثغرة كبيرة فيها.
تذكر المراجع العربية أن الوفد الذي قدِم من بجاية إلى الإخوة بربروس في جيجل كان قبل مناوشة بجاية الأولى، إلا أن خير الدين أورد في مذكراته أن هذا الوفد قدم إلى جيجل قبل مناوشة بجاية الثانية كما أسلف. فيذكر المؤرخ الجزائري "أحمد توفيق المدني" أن المسلمين في جيجل والجبال المحيطة بها قد التفوا حول عروج ورأوا من أيمانه وأخلاقه ومن قوة شخصيته ما جعلهم يبايعونه أميرًا عليهم، ويعاهدونه على السير وراءه في القتال. وهكذا تمكن عروج من إنشاء جيش منظم، وعوده على استعمال الأسلحة الجديدة للرماية، وقد وعده الشيخ أحمد بن القاضي شيخ بلاد زواوة الغربية (كوكو) بالإعانة والتأييد، وأخذ علماء الدين يستنفرون الناس إلى الجهاد وعمت الدعوة وانتشرت. فانطلق عروج إلى بجاية في أغسطس 1514م/جمادى الآخرة 920هـ يقود جيشًا مؤلفًا من عشرين ألف مقاتل، وأحاط بمدينة بجاية، واشتبك مع حاميتها في معارك كبيرة، وكان في نفس الوقت يدرس الموقع ويحاول اكتشاف نقاط الضعف فيه، وبعد مرور ثلاثة أشهر لم يستطع عروج فتح المدينة ورجع بجيشه إلى مركزه في مدينة جيجل خلال شهر نوفمبر/رمضان لكي يقضي الشتاء فيه ويعيد ترتيب جيشه وتزويده. وتذكر مراجع أخرى (ذكر "أحمد توفيق المدني" هذه المناوشة كمناوشة ثالثة) أن البحارة الأتراك بقيادة عروج خرجوا من مدينة جيجل في ربيع سنة 1515م للهجوم عليها ثانية، وقد كان عروج يقود جيشًا بريًا قدرته المراجع بحوالي عشرين ألف مقاتل، كما أمر أسطوله البحري بالتوجه إليها، والتقى الجيشان البري والبحري شرق بجاية في مصب وادي الصومام حيث ما زالت مياهه صالحة للملاحة، فاقتحمته سفن الأسطول ليتم إحكام حصار المدينة من كل الجهات، وشرع في الهجوم العام الذي استمرت معاركه أربعة وعشرين يومًا. ولطول الصحار وشراسة المعارك نفذ البارود من الجيش، وكان عروج قد طلب من سلطان تونس تزويده بالبارود الكافي للحصار، لكن الأخير تماطل في إرساله، ولذلك أوقف عروج الحصار وفشل في تحرير بجاية للمرة الثانية. وكان من نتائج هذه المعارك أن فقد الإسبان حوالي ألفين بن قتيل وأسير وجريح، كما فقد عروج حوالي ربع قواته البرية والبحرية، واضطر إلى حرق سفن الأسطول التي دخل بها إلى وادي الصومام بعد جفاف مياهه، وعاد مع من بقي من جيشه عن طريق البر إلى مدينة جيجل. وتذكر مراجع أخرى أن الحصار دام لثلاثة أشهر لأن مدة أربعة وعشرين يومًا غير كافية لأن تخف فيها مياه النهر بهذا الشكل.
يذكر خير الدين في مذكراته أنه بعد مرور تسعة وعشرين يومًا على حصار بجاية وعدم تمكنهم من فتحها، وصلتهم أخبار تحرك قوات إسبانية كبيرة من منورقة متجهة إلى بجاية، فانسحبوا إلى مركزهم في مدينة جيجل لترصد هذه القوات، وعندما لاحت لهم كانت مكونة من عشرة سفن مشحونة بالأسلحة والمعدات العسكرية، فقاموا بالهجوم عليها واشتبكوا معهم في معركة كبيرة أسفرت عن استيلائهم على جميع السفن، ولم يبق من الجنود الإسبان على قيد الحياة سوى ثمانية وسبعين جنديًا أخذوهم أسرى وقيدوهم ليعملوا في الجدف. فقام خمسمائة بحار بقيادة خير الدين بالكمون في السفن الإسبانية، واتجهوا إلى قلعة بجاية حيث كان الإسبان المتحصنين فيها ينتظرون القطع البحرية العشرة القادمة من منورقة لإمدادهم. وعند دنوهم من القلعة فتح الإسبان أبواب القلعة وتدفقوا على قصورهم الساحلية لاستقبال السفن التي جاءت لنجدتهم، وفجأة أمر خير الدين بحارته بالخروج إلى الساحل، ويضيف خير الدين في مذكراته أن الإسبان عند سماعهم أصوات التهليل اضطربت صفوفهم وولوا منهزمين، فتمكنوا من فتح القلعة، وراح الإسبان يطلبون الأمان. وبعد فتح القلعة جاء جميع شيوخ وقواد المناطق المجاورة لبجاية مبايعين لخير الدين، وانتصب عروج وخير الدين ملكين على هذه البلاد. رجع خير الدين إلى جيجل التي كان أخاه عروج متواجدًا فيها وهنأه بالفتح. استطاع خير الدين في هذه الحملة الاستيلاء على ثمانمائة برميل من البارود (سُرَّ البحارة بالبارود بصفة خاصة حيث لم يعد سلطان تونس يزودهم به، وأصبح يعرض عنهم)، وعددًا كبيرًا من الغنائم. وتذكر المراجع أن الإسبان استطاعوا استرداد مدينة بجاية في الحال.
بينما كان الأخوين عروج وخير الدين متواجدين في مدينة جيجل وصلت وفود عديدة من مدن الجزائرية تطلب من البحارة تحرير مدنهم من الاحتلال الإسباني ومن الأمراء المحليين المتعاونين معهم. كان أهم هذه الوفود وفد مدينة الجزائر التي تمثل مركز البلاد، وقد طلب هذا الوفد من البحارة بقيادة عروج القدوم إلى مدينة الجزائر لطرد الإسبان والقضاء على "حصن البنيون" أو "حصن الصخرة" الذي قاموا ببنائه سنة 916هـ/1510م على جزيرة صخرية تقع في مدخل المدينة وتبعد هذه الجزيرة عن مدينة الجزائر مسافة ثلاثمائة متر، وقد كان هذا الحصن مصدر إزعاج واعتداءات مستمرة ضد سكان المدينة، وكان تمركزهم فيه قد مكنهم من التحكم بمدخل ومخرج المدينة، فتسببوا بشل الأعمال البحرية الجزائرية وضيقوا على السكان وفرضوا عليهم الضرائب. على هذا، خلَّف عروج أخاه خير الدين على مركزهم في مدينة جيجل، وقرر المسير نحو الجزائر في خمسمائة بحار كما في مذكرات خير الدين، وتذكر المراجع العربية أنه خرج برًا في ثمانمائة بحار، وحمَّل ست عشرة سفينة بالمدفعية والذخيرة وأرسلها مع نصف جنوده، وفي طريقه انضم إليه خمسة آلاف من مقاتل من القبائل الجزائرية. وتنص مصادر أخرى أنه خرج في ثمانمائة بحار، وأرسل أخاه خير الدين على ظهر ثماني عشرة سفينة تحمل ألفًا وخمسمائة مقاتل؛ إلا أن هذا القول يتعارض مع ما ذكره خير الدين في مذكراته من أنه استقر في مدينة جيجل. وتوجه عروج إلى مدينة شرشال أولًا وفتحها، وترك فيها حامية عسكرية لحراستها، تنص بعض المصادر أن سبب ذهابه إلى شرشال أولًا كان القصد منه تأمين مكان للالتجاء إليه في وقت الشدة، أو أنه كان ينتظر وصول بعض المهاجرين الأندلسيين لضمهم إليه وكسبهم إلى جانبه، أو أنه بانتظار أخيه الذي أرسل إليه خبرًا بضرورة الالتحاق به، وبهذه الحركة يكسب زمنًا كافيًا لدراسة الموقف بوضوح تام. يجمع المؤرخون أن عروج حين دخل إلى مدينة الجزائر سنة 921هـ/1516م استقبله الأعيان والأمراء ووجهاء المدينة وأعداد كبير من أهلها استقبال الفاتحين المنقذين، ورحبوا به ترحيبًا حارًا.
عندما كان عروج في طريقه إلى مدينة الجزائر غادر خير الدين مدينة جيجل متجهًا إلى تونس، وقد نص في مذكراته على أن سلطان تونس قد جاهر بعداوتهم، إلا أنه عندما رأى خير الدين مقبلًا على تونس خشي على نفسه وتظاهر بثنائه عليهم واعتذر على تقصيره في عدم تزويد البحارة بالبارود، ويذكر خير الدين أنه تظاهر بانخداعه بكلامه وتجول معه في مدينة تونس، ثم عاد إلى المرسى. وقفل راجعًا إلى جيجل برفقة أخيه إسحاق بعد أن وجه رؤساء البحر ومنهم بعض الرؤساء المشاهير مثل: "كوردوغلو مصلح الدين ريس" و"دلي محمد ريس" بالتوجه إلى الغزو في شرق البحر الأبيض المتوسط ونواحي قبرص فخرجوا في سبع قطع بحرية، وقد صادفوا في طريقهم بين قبرص ومصر الأسطول العثماني فتتبعوه حتى دخلوا ميناء الإسكندرية، وفي هذه الأثناء كان السلطان سليم الأول معسكرًا في القاهرة بعد أن أتم فتح مصر، والتقى السلطان سليم بمصلح الدين واحتفى به، وأمده بعدد كبير من الجنود ومعدات الحرب، وعاد بها إلى الجزائر.
تنص المراجع أن عروج حالما وصل إلى مدينة الجزائر بعث إلى قائد الحامية الإسبانية في حصن بنون يأمره بالاستسلام وتسليم القلعة إليه، فرد عليه الأخير بالنفي، فوجه عروج مدافعه نحو الحصن وبدأ بقصفه واستمر على ذلك مدة عشرين يوم، إلا أن مدافعه كانت ضعيفة ولم تؤثر على الحصن، وهذا ما جعل الأهالي يفقدون ثقتهم بالبحارة الأتراك، وتذكر بعض المراجع العربية أن البحارة كانوا يعاملون السكان معاملة فضة، وبعد فقدان ثقتهم بهم توجه السكان بقيادة "سالم التومي" الذي كان هو الحاكم السابق للمدينة بالاتفاق مع الإسبان على طرد الأتراك من الجزائر وقد كان يهدف لاسترجاع سلطته ونفوذه السابق، وما إن علم عروج بهذا الاتفاق حتى اعتبره خيانة له، فأمر بقتل سالم التومي، وبعد هذا أصبح عروج هو صاحب السلطة المطلقة في الجزائر فأعلن نفسه سلطانًا عليها، ورفع فوق أسوارها وقلاعها راياته وبادر بسك النقود التي تحمل شعاره. وفي 2 رمضان 922هـ/30 سبتمبر 1516م شن الإسبان غارة على مدينة الجزائر، حيث أرسلوا أسطولًا مكونًا من حوالي خمسة وثلاثين إلى أربعين سفينة محملة بالجنود، ودارت بينهم وبين عروج وجيشه من الأتراك والجزائريين والمهاجرين الأندلسيين معركة كبيرة بانتصار عروج انتصارًا حاسمًا.
كتب عروج إلى خير الدين الذي كان متواجدًا في جيجل يبشره بالنصر، وعندما وصله كتابه كان يستعد للخروج برفقة أخيه الأكبر إسحاق ريس إلى الجزائر في عشر قطع بحرية لمساعدة عروج، ولما لم تعد هناك حاجة لذلك خرجوا إلى الغزو فاستولوا على ست عشرة قطعة بحرية محملة بالبارود والرصاص والألواح والقطران والزيت والرز والقمح، ورجعوا إلى جيجل بعد مرور تسعة وعشرين يومًا على خروجهم. ثم وصله كتاب آخر من عروج بعد رجوعه إلى جيجل يأمره فيه بالقبض على أحد الشيوخ الذي كان يخبر الإسبان بتحركات عروج، فخرج خير الدين بخمسمائة بحار إلى الجبال وقبض على هذا الشيخ وأمر بضرب عنقه وعين شيخًا آخر بدلًا عنه.
بعد بضعة أيام توجه خير الدين في أكثر من عشرين سفينة إلى ميناء الجزائر حيث اجتمع هناك بإخوته إسحاق وعروج. وقد كان عروج يريد أن يضم مدينة تنس إلى نفوذه وتذكر بعض المراجع أن أهل مدينة تنس أرسلوا له وفد يطلب منهم تحرير المدينة من حاكمها من الأسرة الزيانية المتعاون من الإسبان والذي جعل سلطنته تحت حمايتهم، فتوجه خير الدين إلى تنس في عشرة سفن، فصادف أربع سفن إسبانية راسية في الميناء، وعندما رأى الجنود الإسبان البحارة بقيادة خير الدين هرعوا إلى القلعة محتمين بأسوارها، فاستولوا على سفنهم ومدافعهم وبنادقهم، ونزل خير الدين بألف وخمسمائة جندي وعسكر أمام القلعة متوقعًا مقاومة شديدة، إلا أنه وجد أبواب القلعة مفتوحة وقد خرج لاستقبالهم بضع مئات من سكان المدينة مرحبين بهم وبايعوا عروج سلطانًا عليهم، وأخبروهم بأن أمير تنس الزياني ورجاله قد هربوا مع الإسبان، فأرسل خير الدين خلفهم ألفي مقاتل حتى أدركوهم ودارت بينهم معركة انتهت بأسر ثلاثمائة وخمسين جنديًا من الإسبان وأما بقيتهم فقد قتلوا، بينما فقد خير الدين من مقاتليه سبعين أو ثمانين. قام خير الدين بتعيين أحد الضباط نائبًا على المدينة وتوجه في ست عشرة قطعة بحرية إلى الجزائر. عندما رجع خير الدين إلى الجزائر استطاع أمير تنس السابق الرجوع إلى المدينة بعد بمساعدة من الإسبان ومن عمه سلطان تلمسان، فثارت ثائرة عروج بعدما سمع هذا الخبر وقرر أن يسير إلى تنس بنفسه واستصدر فتوى من علماء الجزائر الذين أباحوا دم أمير تنس لأنه متعاون مع الإسبان، وبعد وصوله إلى هناك في جمادى الأولى 923هـ/يونيو 1517م قام أهالي تنس بتقييد الأمير الزياني وسلموه إلى عروج فأمر بضرب عنقه، ودعا بعدد من رؤساء العرب الذين بايعوه للمثول بين يديه وأمر بضرب أعناقهم أيضًا، وهكذا دخلت تنس تحت نفوذه. ودخلت عدد من المدن الجزائرية تحت نفوذه كذلك وهي المدية ومليانة والبليدة. يذكر المؤرخون أن عروج عامل أخاه خير الدين كمعاملته لنفسه فقام بتقسيم مملكته الجديدة إلى قسمين مقاطعة شرقية يشرف عليها أخاه خير الدين ومقرها مدينة دلس، ومقاطعة غربية يشرف عليها بنفسه ومقرها الإداري مدينة الجزائر العاصمة، وكانت كل مقاطعة تضم خمس بلديات.
كانت مملكة تلمسان تحكم من قبل الأسرة الزيانية وقد كان حكامها تحت الحماية الإسبانية، وفي سنة 923هـ/1517م ثار الأهالي على السلطان ففر هاربًا، وأرسلوا وفدًا إلى عروج يبايعونه سلطانًا عليهم، سر عروج بهذا لدخولهم تحت سلطانه بدون قتال. أحدثت دعوة أهالي تلمسان لعروج ليكون سلطانًا عليهم فزعًا كبيرًا لدى الإسبان فقد كانت تلمسان خاضعة لتسلطهم ونفوذهم، فأمر عروج بقطع جميع العلاقات مع وهران حيث كان متمركزين فيها وقد كان القائد الإسباني الأكبر في إفريقيا مقيمًا فيهم. توجه عروج إلى تلمسان بقواته وذلك بعد أن ترك أخاه خير الدين نائبًا له في الجزائر. وفي طريقه واجه جيش مكون من من ثلاثة آلاف جندي وستة آلاف خيال بقيادة السلطان الهارب إلا انه انتصر عليه وأكمل طريقه. وما لبث عروج هناك حتى أعلن نفسه حاكمًا على تلمسان. ثم جمع الإسبان جيشًا كبيرًا وانضم لهم سلطان تلمسان الهارب "أبو حمو" بجيشه، بهدف إرجاع الأخير إلى عرش تلمسان، فخرج عروج لملاقاتهم ودارت بينهم معركة كبيرة انتهت بمقتله وكان ذلك في شهر جمادى الأولى سنة 924هـ الموافق مايو 1518م. وقد قتل "إسحاق ريس" قبل ذلك ببضعة أشهر في قلعة بني راشد "قلعة القلاع" وقد كانت وفاته في أواخر شهر محرم/يناير من نفس العام.
بعد وفاة عروج اتفق جميع أصدقائه البحارة على تسليم القيادة من بعده إلى أخيه خير الدين وقد كان ذلك في سنة 924هـ/1518م، وفي الوقت نفسه كان خير الدين متأثرًا بشكل كبير بهزيمة أخيه عروج ومقتله مع أفضل العساكر، وعلاوة على ذلك فقد تخلى عنه بعض أصدقائه من قادة البحارة لعدم ارتياحهم له ولشعورهم بأن خير الدين لن يستطيع أن يكون بديلًا عن عروج. وفي الوقت نفسه واجه خير الدين موقفًا عصيبًا ودقيقًا فقد انتفضت عدد من النواحي على حكم الأتراك بعد وفاة عروج، فثارت بلاد زواوة تحت قيادة أحمد بن القاضي، واستغل سلطان تونس هذه الفرصة فأرسل إلى خير الدين يطلب منه أن يعترف بسلطنة تونس ويخضع لها، بالإضافة إلى توقع خير الدين بسير الإسبان إلى الجزائر للقضاء عليه بعد أن تمكنوا على أخيه. وضعت كل هذه الشروط الصعبة لدى خير الدين فكرة الرحيل من الشمال الإفريقي والتوجه إلى إسطنبول.
ويذكر المؤرخ "أحمد توفيق المدني" أن أهل الحل والعقد اجتمعوا بمدينة الجزائر وعرضوا على خير الدين أن يتولى الإمارة بعد أخيه بإلحاح شديد، وأن يواصل الجهاد في سبيل الله، لكنه اعتذر عن قبول ذلك وصرح لهم بعزمه على استئناف الغزو والجهاد على متن البحار، وأنه يعتزم السفر إلى إسطنبول مستمدًا منها أسطولًا للجهاد، فقال له العلماء: "إن الله يوجب عليك البقاء في هذه المدينة الإسلامية ولا يسمح لك الدين بتركها نهبة للمفترس"، وقد نقل المؤرخ أحمد بن أبي الضياف ما دار بين خير الدين وبين أعيان الجزائر فيقول: ""بأنه بقي منفردًا دون إخوته (الذين استشهدوا جميعًا في الجزائر) وقد رأيتم ما فعله بنا صاحب تلمسان من بني زيان، واستعانته علينا بغير ملتنا حتى كفانا الله أمره، وصاحب تونس الحفصي لا رأي له في نصرتنا واعانتنا، واسلمنا للعدو بمنع البارود عنه (أثناء حملة بجاية) لولا لطف الله، فالرأي هو أن نصل أيدينا بالقوة الإسلامية -وهو السلطان سليم خان- ونعتمد عليه في حماية هذه المدينة، ولا يكون ذلك إلا ببيعته والدخول في طاعته، بالدعاء له في الخطب على المنابر، وضرب السكة باسمه، لنتفيأ ظل حمايته...""
أثناء هجوم الإسبان على تلمسان تمردت تنس وشرشال لدى عودة حكامها القدامى، وبنفس الوقت بدأ أحمد بن القاضي يحرض الأهالي والقبائل ضد خير الدين لكي تخلو الساحة له، إزاء ذلك كلف خير الدين عساكره ومؤيديه بالتوجه إلى تنس وشرشال لتأديبهما، في حين ترك القبائل القوية إلى وقت آخر، لأن الوقت غير مناسب لمثل ذلك، واتبع خير الدين سياسة الحكمة والدهاء وهذا ما جعل العلماء يقفون بجانبه، وتعاهدوا سوية على طرد المسيحيين من البلاد، كما أجبر قسمًا كبيرًا من الأهالي على مساندته وتأييده في العلن والتخلي عن معاداته. وكذلك كانت من المشاكل التي عانى منها خير الدين مشكلة تأمين السلاح والبارود حيث أن أبو حمو بعدما تسلم الحكم ثانية في تلمسان امتد نفوذه حتى مليانة، فغدا بذلك على مقربة من مدينة الجزائر. ويذكر المؤرخون أن خير الدين اتصف بالحنكة السياسية بالإضافة إلى الشجاعة والإقدام، فحسن تصرفه وهدوء اعصابه تجاه الأزمات مكنه من تحقيق أعمال عجز عن تحقيقها أخاه عروج، فهو لم يكن يعرض نفسه للخطر إلا بشكل نسبي وبالحدود التي ترهب أعداءه، وقبل القيام بتنفيذ عمل كان يقوم بدراسته وفهم أبعاده ومحصلة نتائجه، وكان يبتعد عن زج نفسه في أي خطر لا لزوم له، وبنفس الوقت إذا اتخذ قرارًا ما كان يعمل على تنفيذه تنفيذًا كاملًا، فم يعتاد أن يفرط في حق طالما يعتقد بضرورته وفوائده، وحينما يعتمد توجيه أي ضربة، قلما يستطيع أي إنسان آخر توجيهها مثله.
أدرك خير الدين بمحاكاته للواقع الذي يتعايش معه أنه بحاجة إلى دولة قوية تحميه، ويستند عليها في أوقات الشدة والضيق، وآنذاك كان نجم الدولة العثمانية يسطع كأقوى نجم، وكانت حكومتهم أقوى حكومة يمكن من خلالها ضمان وجوده وتقوية نفوذه، إضافة إلى أنها دولة إسلامية إطارها العالم الإسلامي وتتوجه نحو حماية الإسلام، لذلك قرر الرجوع إليها والدخول تحت حمايتها. فقام خير الدين على أثر ذلك بإرسال "حاجي حسين آغا" الذي كان من أوثق رجاله إلى السلطان العثماني سليم الأول في إسطنبول، وبعد وصوله استقبله السلطان استقبالًا حسنًا وأكرمه هو ومن معه من البحارة، وبعد أن مكث في العاصمة العثمانية واحدًا وأربعين يومًا أزفت ساعة رحيلهم، فأمر السلطان أن تمر السفن الجزائرية قريبًا من قصره الساحلي لكي يتفرج عليها، فقامت السفن بالاستعراض بين يديه وهي تطلق القذائف تحية له. وقبل مغادرته لإسطنبول قام حسين آغا بزيارة وداع للسلطان، وفي هذه الزيارة سلمه السلطان فرمانًا ورد فيه أمر تعيين خير الدين "بكلربك" (أمير الأمراء) على الجزائر، ثم سلمه سيفًا مرصعًا وخِلعة مذهبة وراية الإمارة. ويذكر المؤرخون وجود وثيقة محفوظة في قصر طوب قابي في إسطنبول وهي عبارة عن رسالة موجهة من سكان الجزائر على اختلاف مستوياتهم ومؤرخة في أوائل شهر ذي القعدة عام 925هـ في الفترة من 26 أكتوبر إلى 3 نوفمبر عام 1519م وكتبت بأمر خير الدين إلى السلطان سليم بعد عودته من مصر والشام إلى إسطنبول، وكان الغرض من تلك الرسالة ربط الجزائر بالدولة العثمانية، وجاء في الرسالة أن خير الدين كان شديد الرغبة في أن يذهب بنفسه إلى إسطنبول ليعرض على السلطان سليم الأول شخصًا أبعاد قضية الجزائر، ولكن زعماء مدينة الجزائر توسلوا إليه أن يبقى فيها كي يستطيع مواجهة الأعداء إذا تحركوا. وطلبوا منه أن يرسل سفارة تقوم بالنسبة عنه وكانت الرسالة التي حملتها البعثة موجهة باسم القضاء والخطباء والفقهاء والأئمة والتجار والأعيان وجميع سكان مدينة الجزائر. وبعد رجوع حسين آغا مع الوفد إلى الجزائر قبل خير الدين هدايا السلطان سليم باحترام، ثم جمع ديوانه والأهالي وأعلن تبعيته رسميًا للعثمانيين. وقام السلطان بحل مسألة احتياج خير الدين للسلاح، ثم أرسل له ألفان من مسلحين بالبنادق، وعددًا من رجال المدفعية مع مدفعيتهم، وعددًا من المتطوعين، كما أعلنت الدولة العثمانية عن تأمين مصاريف الطريق للراغبين بالذهاب إلى الجزائر، ووعدتهم بالحصول على الامتيازات التي يحصل عليها الانكشاريون. وتذكر مراجع أخرى عدد الجنود والمتطوعين الذين أرسلهم السلطان أربعة آلاف شخص.
يذكر المؤرخان "عزيز سامح التر" و"مبارك الميلي" أن أهالي الجزائر حينما لمسوا أن الأتراك يسعون جادين إلى تثبيت وجودهم فيها، اتفقوا مع القبائل المجاورة على سحقهم في يوم البازار (سوق البيع). فدخلت القبائل التي تقطن في السهول المجاورة إلى مدينة الجزائر حخفية ومعهم أسلحتهم، في حين ذهب قسم منهم إلى الساحل حيث ترسوا سفن البحارة الأتراك من أجل حرقها، وذلك وفقًا لخطتهم المرسومة، فحينما يشاهد البحارة أن النار تشتعل في سفنهم، يسرعون لإطفائها، وحالما يخرجون من المدينة يقوم الأهالي بإغلاق أبواب المدينة، ومن بعد ذلك يقومون بقتل من تبغى منهم، لأن أعدادهم ستكون قليلة، وبهذه الطريقة يتخلصون من الأتراك، لكن جواسيس خير الدين أعلموه بما تم الاتفاق عليه، فألقى الفبض على المخططين منهم، وقطع رؤوسهم وعلقها على باب القصر بعدما مثل بجثثهم، فخمدت ثورة الأهالي، وخافوا من إعلان التمرد بعد ذلك التاريخ.
يذكر خير الدين في مذكراته أنه عندما وصل خبر وفاة أخيه عروج قرر أن يعيش لغاية واحدة وهي المضي في نفس الطريق الذي سلكه أخوه، وتتمثل تلك الغاية في التضييق على الأوروبيين غير المسلمين في إفريقيا والبحر الأبيض المتوسط. فأخذ العديد من الاحتياطات والتدابير، ولكن الإسبان لم يجدوا قوة تمكنهم من القدوم إلى الجزائر. وقضى فترة الشتاء في الاستعداد، فقام بإصلاح وتجديد جميع سفنه ومدافعه ومعداته. ويذكر أيضًا أن رسول بعثه الملك الإسباني كارلوس الخامس جاءه وقال له: ""لقد مات أخوك وقتل أكثر جنوده فكُسِر جناحك، من تحسب نفسك حتى تقف في وجه أقوى ملك مسيحي بدون أخيك؟ ماذا يمكنك أن تفعل؟ خذ سفنك ورجالك وأخرج من الجزائر فورًا، وإياك وأن تطأ قدماك إفريقيا مرة أخرى، إن هذا آخر إنذار أوجهه إليك، سوف أملأ البحر بالسفن وأعود إلى الجزائر قريبًا، فإذا تمكنت منك هناك، فلتعلم بأن عاقبتك ستكون وخيمة."" في نفس الوقت كان خير الدين يُعرف في أوروبا باسم "ملك الجزائر" وكان في نفس الوقت في منصب بكلربك لدى الدولة العثمانية فرأى خير الدين أن مخاطبة ملك إسبانيا له بهذا الاستخفاف تستلزم أن يوقفه عند حده، ولذلك كتب له خطابًا شديد اللهجة وأرسله إليه. وعندما استلم رده أرسل أساطيل سدت الأفق، اشترك فيها ملوك نابولي وصقلية وألمانيا وهولندا وبلجيكا الذي كانوا تابعين لكارلوس. فرست سفنهم قبالة ساحل الجزائر حيث قاموا بإنزال قواتهم إلى البر. وقد كان خير الدين قد استعد جيدًا إذ أنه توقع ردة فعله، وما إن أنزلوا قواتهم حتى قام خير الدين وجنوده بقتل عدد كبير منهم، بينما استسلم سبعمائة إلى ثمانمائة منهم من أصل عشرين ألف، وأما الباقون فقد لاذوا بالفرار إلى سفنهم، بينما عاد ملوك كارلوس وقادته مهزومين.
تذكر بعض المراجع هذه المعركة بروايات مختلفة عن التي ذكرها خير الدين في مذكراته -والتي سلف ذكرها- حيث لم يفصل الأخير بأحداث المعركة. بينما أسهب بعض المؤرخين في الحديث عن المعركة المذكورة فيذكر "أحمد توفيق المدني" و"عزيز سامح التر" أن الإسبان لم يصبروا على الهزيمة التي أصيبوا بها تحت أسوار مدينة الجزائر في السنة الماضية على يد عروج فأخذوا يستعدون للأخذ بالثأر، وقد زاد إعلان انضمام الجزائر للدولة العثمانية هلعهم، ومن ثم وصول الخطر العثماني إلى هذا القسم الغربي من البحر الأبيض المتوسط الذي كان تحت السيطرة الإسبانية، فقد كانت أهم المدن الساحلية الجزائرية ومعظم السواحل الإيطالية تحت سيطرتهم. ولقد اغتنم الإسبان فرصة مقتل عروج وانتصارهم في تلمسان وما أحدثه ذلك في كل البلاد الجزائرية من حزن وأسى، فاتفقوا مع أبي حمو ملك تلمسان على أن يشترك الجانبان في التخلص من خير الدين ودولته الناشئة، وذلك بأن يهاجم الإسبان من البحر في نفس الوقت الذي تتقدم فيه نحوها جيوش صاحب تلمسان. وقد كانت هذه الحملة الاسبانية تشمل أربعين سفينة كبيرة، تحمل على متنها خمسة آلاف مقاتل. وقد وصل الأسطول إلى الجزائر في يوم 19 شعبان 925هـ الموافق 17 أغسطس 1519م، واختار الجيش الإسباني الساحل الممتد على يسار وادي الحراش ميدانًا لعملياته، وكانت الخطة التي رسمها خير الدين تجعل هذه المعركة تكاد تكون طبق الأصل للمعركة التي جرت خلال السنة الماضية؛ أي أنهم يتركون الجيش الإسباني ينزل إلى البر في النقطة التي يختارها فيضع سلاحه وعتاده، ثم يناوشونه في حرب كمين محيطين به من كل جهة، حتى ينهكه التعب ثم يلتحمون به في معركة فاصلة في الساعة التي يرونها مناسبة. وهكذا كان، فقد أنزل الإسبانيون جندهم وسلاحهم وأمتعتهم، جاعلين وراءهم وادي الحراش، وانقضت أوقات قليلة في مناوشات بين الجانبين، ولم يدر الجزائريون بقيادة خير الدين ما هي النقطة التي سيركز الإسبان هجومهم عليها، إلى أن تحرك الجيش بكامل قوته، وأخذ يصعد المرتفعات المحيطة بالجزائر حتى وصلوا إلى "كدية الصابون" المشرفة على المدينة من ورائها، وأخذوا بسرعة في بناء قلعة فوق الكدية ودعوها "قلعة الإمبراطور". وتم تجهيز القلعة بالمدافع الثقيلة ووضعوا الجزائر تحت تهديد مدافعهم، إلا أن مهارة خير الدين الحربية كما يذكر المؤرخون لم تمكنهم من ذلك، فلم تصب مدافعهم إلا الأسوار الخلفية دون أن تلحق بها أذى. وفي نفس الوقت الذي كان فيه الإسبان يقومون فيه ببناء القلعة، كانوا ينتظرون قدوم الجيش التلمساني والذي كان ركنًا أساسيًا في هذه المعركة المقبلة، لكن انتظارهم دام ستة أيام، وتم بناء القلعة، وأرهقت المناوشات الجيش الإسباني، وعندما لم يظهر أثر لجيش تلمسان قررت القيادة الإسبانية البدء بالهجوم. بدأ الإسبان هجومهم، وخلال يومين من بدء المعركة ظهرت علامات الإعياء والإنهاك على القوات الإسبانية، فبدأت بالتراجع والانسحاب، وفي اليوم الثالث شكل خير الدين فرقة من خمسمائة مقاتل، وكلفها بتدمير المعسكر الإسباني وحرق قواربهم، خدع الإسبان بالفرقة التي شكلها خير الدين، فأعدوا قوة لمهاجمتها تاركين مواقعهم الدفاعية، فاستغلت قوات خير الدين فرصة انسحابهم، وانقضوا بكل قواهم على الإسبان، وأحدثوا خللًا وإرباكًا في صفوف الإسبان، فاضطر البعض منهم إلى تسليم نفسه بدون قتال، وغدت القوات الإسبانية وسط دهشة كبيرة محاصرة من ناحية البر، ولم يبق أمامهم سوى البحر، فاندفعوا إلىيه تاركين سلاحهم وعتادهم في ساحة القتال. وأثناء هذه العملية أخذت أمواج البحر ترتفع واشتد هيجان المياه، وهذا ما جعل الرجوع إلى الأسطول أمرًا غير ممكن، فلم يستطع الوصول إلى الأسطول إلا القليل، وقد بقي أكثر الجيش على الساحل فقتل بعضهم، واستسلم البعض الآخر، وكان عدد الأسرى يزيد عن الثلاثة آلاف أسير الذين قتلوا أيضًا -يذكر بعض المؤرخين أن قتلهم كان انتقامًا على مقتل إسحاق بن يعقوب أخ خير الدين الأكبر الذي قتل بعدما استسلم-، وغرق حوالي الأربعة آلاف شخص. وقد كان يوم هذه المعركة هو 26 شعبان 925هـ الموافق 24 أغسطس 1519م أي أن المعركة استمرت لمدة ثمانية أيام. ويُذكر أيضًا أن أربعة وعشرين سفينة من الأسطول الإسباني المتبقي أرجعتها الأمواج إلى الساحل الجزائري بكل ما فيها.
يذكر "عزيز سامح التر" أن خير الدين في ربيع سنة 927هـ/1520م أرسل قوة إلى تنس لضمها إلى نفوذه، فطلب قائد تنس النجدة من إسبانيا، فقدمت خمس عشرة سفينة لمساعدته، ولكن خير الدين أرسل ثمان عشرة سفينة لدعم القوة التي أرسلها سابقًا، وقاد بنفسه قوة بحرية أخرى، وتوجه مباشرة إلى تنس وضم قلعتها، وأسر خمس سفن إسبانية، ومن بعدها عاد إلى الجزائر.
أورد خير الدين في مذكراته أن أحد أمراء بني زيان وهو "الأمير مسعود" قدم إليه في الجزائر طالبًا مساندته ضد أخيه الأكبر "مولاي عبد الله"، فقام خير الدين بإرسال قوة مكونة من ثلاثة آلاف فارس معه، وألف راجل. وقد كان سبب إرساله لهذه القوة حسب ما ذكر في مذكراته أن جواسيسه أعلموه بأن سلطان تلمسان "مولاي عبد الله" بدأ يثير الناس هناك ضد خير الدين ويتكلم عنه بسوء. وهكذا فإن مولاي عبد الله ما إن علم بوصول قوات خير الدين حتى لاذ بالفرار إلى وهران مستغيثًا بالإسبان. أما الأمير مسعود فقد حقق انتصارًا باردًا لم يرق فيه قطرة دم، ودخل تلمسان وجلس على عرشها. وكافأ عساكر خير الدين والمتطوعين العرب الذي شاركوا معه، وبعث إلى خير الدين بخمسين ألف قيمة الخراج السنوي، بالإضافة إلى عدد كبير من الهدايا. ثم كتب خير الدين خطابًا له قال فيه:
وأشار خير الدين في مذكراته أن مسعود ما إن جلس على العرش حتى شرع في ظلم الناس ونهب أموالهم بغير حق، وعلم بأنه مزق كتابه الذي بعثه إليه ما إن قرأه. فسمع أخوه الكبير اللاجئ بوهران بما فعله فاتصل بخير الدين، وطلب منع إعادته إلى العرش ووعده بأنه سيكون تحت طاعته، فأراد خير الدين أن يضربه بأخيه مسعود فقام بالعفو عنه. وفي هذا الوقت كان خير الدين راسيًا في مستغانم التي فتحها بدون عناء، وقد كانت قريبة من وهران التي كانت تحت يد الإسبان. فقدم إليه "الأمير عبد الله الزياني" وأرسل معه ألفًا من رجاله إلى تلمسان. وفي نفس الوقت كان خير الدين منشغلًا بإسكان ألفين ومائتين وخمسة وثمانين مهاجرًا أندلسيًا في نواحي مستغانم كان قد حملهم في سفنه من إسبانيا، فوهب لهم أراضي يقومون باستصلاحها والعمل فيها.
وصل "الأمير عبد الله الزياني" إلى تلمسان وصار حاكمًا عليها، بينما تحصن أخوه "مسعود الزياني" بالقلعة خمسة وعشرين يومًا. وبعد ذلك قام البحارة الذي أرسلهم خير الدين بجانب الأمير عبد الله بالقيام بخدعة حربية بسبب عدم امتلاكهم للمدافع، وتمثلت الخدعة في رفعهم للحصار والتظاهر بالفرار، وعندما شاع بين أنصار الأمير مسعود فرارهم دفعهم الاستيلاء على الغنائم إلى تعقبهم، ثم ارتد البحارة عليهم واستولوا على القلعة وسلموها للأمير عبد الله. وبعد سقوط القلعة فر السلطان مسعود مع خمسة أو عشرة من رجاله دون أن يعرف أحد مصيرهم، وقد تخلى عن ستة آلاف من المقاتلين البدو الذين تحصن بهم في القلعة وهرب منها دون أن يخبرهم، حتى أنهم استمروا في التصدي لبحارة خير الدين وهم لا يعلمون أن سلطانهم قد هرب، وعند علمهم بذلك أعلنوا استسلامهم. في معركة تلمسان هذه قام بحارة خير الدين بقتل خمسة آلاف بدوي وعفوا عمن ألقوا سلاحهم واستسلموا. وفي يوم الجمعة قرئت الخطبة باسم السلطان العثماني سليم الأول دلالة على التبعية له. وبعد ذلك ترك بحارة خير الدين تلمسان بعد تركوا فيها مائة منهم بطلب من السلطان.
يذكر خير الدين في مذكراته أنه منذ استقراره في الجزائر كان مضطرًا للانشغال بالأمراء المحليين وأشباههم في الجزائر وتونس والمغرب الذين كانوا مستائين من وجود الأتراك في الشمال الأفريقي. فشرع ملوك وأمراء تونس وتلمسان بالتحالف مع الإسبان وحبك المؤامرات ضدهم في السر والعلن، ويذكر أيضًا أن سبب ذلك هو أن سلطان تونس كان متوجسًا منهم قبل الدخول في حماية العثمانيين، وقد كان يظن أن السلطان العثماني سليم الأول يرغب في ضم تونس، وهكذا ازدادت الهوة بين خير الدين وبين سلطان تونس الحفصي. وازدادت أكثر بعد أن وقعت بيده رسالة أرسلها إلى سلطان تلمسان الزياني وجاء في هذه الرسالة ما ملخصه: ويذكر خير الدين في مذكراته أن بعض القبائل استجابت لتحريض سلطان تونس، فأرسل إليها قوة مكونة من ستة آلاف راجل وستة آلاف فارس، فتم تأديبها.
بعدما فرغ خير الدين من أمر تلمسان وجه تفكيره في حل مسألة "أحمد بن القاضي" الذي أوجز خير الدين في مذكراته الحديث عنه فذكر أنه والده أحد عظماء العرب بالجزائر، وأنه كان يُكن له قدرًا كبيرًا من الصدق والمودة. وقد حاول سلطان تونس الحفصي أن يحرضه على الخروج على خير الدين إلا أنه لم يوافقه على ذلك، وبعد وفاته حل محله ابنه "أحمد" الذي كان أول ما قام به بعد وفاة والده أن اتفق مع سلطان تونس على أن يخرجا الأتراك من بلاد العرب، ويذكر خير الدين أن رسالة بعثها أحمد بن القاضي إلى سلطان تونس الحفصي قبل وفاة والده بشهرين قد وقعت بيده، ومما جاء في تلك الرسالة: وعند وقوع هذه الرسالة في يد خير الدين خرج لحرب سلطان تونس باثني عشر ألفًا من رجاله، ونزل بأحد السهول. وعندما رآه سلطان تونس الحفصي "أبو عبد الله محمد المتوكل" من بعيد ظن أنه حليفه ابن القاضي، فباغته خير الدين بوابل من القذائف جعلت قواته تتشتت، ووقع السلطان في الأسر، فيذكر خير الدين أنه قام بنصحه وحذره من تكرار فعلته، ثم أمر بإطلاق سراحه. وفي هذه المعركة استولى جيش خير الدين على ثلاثمائة خيمة أمر بإرسالها إلى الجزائر، بينما أقام في تلك المنطقة بين خمسة أيام أو عشرة.
أورد خير الدين في مذكراته أنه بعد انتهائه من الحرب مع السلطان الحفصي أعطى أوامره بالتحرك والعودة إلى الجزائر. وفي طريقه استطاع "أحمد بن القاضي" اعتراضه حيث كَمن له في مكان ضيق فأدهش هذا خير الدين، ووقعت بينهم معركة دامت ثلاث ساعات ونصف تمكن فقد فيها سبعمائة وخمسون بحارًا، بعدها من تجاوزه واستطاع هو وجيشه الوصول إلى الجزائر. بدأت حركات العصيان تتوالد في الجزائر، وعمل ابن القاضي على جمع عدد كبير من السكان حوله، وأصبح يراسل كل النواحي ويدعوهم إلى التمرد على حكم الأتراك. وكان ممن استجاب لدعوة ابن القاضي إلى التمرد أحد بحارة خير الدين ويدعى "قرة حسن" حيث طمع في أخذ مكانه والانقلاب عليه فراسل ابن القاضي، وما إن علم خير الدين بذلك حتى قام بطرده. استطاع "أحمد بن القاضي" في نهاية الأمر على جمع جيش قوامه أربعون ألف رجل، وفي نفس الوقت كان خير الدين مستعدًا له حيث كانت تبلغه أخبار ابن القاضي عن طريق جواسيسه، فقام بإرسال عشرة آلاف بحار للتصدي للثائرين. فاشتبكوا معهم في معركة كبيرة فقد فيها خير الدين ألفي بحار وألفي جريح، إلا أن المعركة انتهت بالقضاء على العصاة عن بكرة أبيهم، ولم ينج منهم سوى سبعمائة ثائر. أما بقيتهم فقد تم قتلهم أو أسرهم. وجمع مائة وخمسة وثمانين من رؤساء التمرد مقيدي الأيدي، وجمع علماء الجزائر وطلب منهم الحكم الشرعي فيهم، فأخبروه بأن حكمهم هو الموت لخروجهم عليه، إلا أن بينهم كثيرًا من الغزاة الذي تصدوا للإسبان فإن كان ثمة مجال للعفو فأعف عنهم. وسأل بعدها رؤساء البحارة فأجابه أحدهم بأن هذا الوقت ليس وقت العفو واللطف وأنه يجب قتلهم ليكونوا عبرة لغيرهم. فترجح لخير الدين قول البحار وأمر بضرب أعناقهم.
أشار خير الدين في مذكراته أن أهالي الجزائر لم يكونوا يرغبون بحكم الأتراك وليسوا سعداء بوجودهم ولذلك كان يفكر في الانسحاب منها لكي يعرف أهل الجزائر قيمته على حد تعبيره، وذكر أيضًا أن انسحابه سيلحق أضرارًا بالغة بالحركة التجارية في البلاد، وأن السكان لن يستطيعوا إدارة الجزائر فضلًا عن التصدي الإسبان، ثم سيرجعون إليه مرة أخرى طالبين منه العودة للحكم، فمكث فترة يفكر في هذا الموضوع إلى أن قرر في أحد الأيام أن يحمل بحارته وعائلاتهم وأموالهم في السفن الخمسة والعشرين التي كانت راسية في الميناء، وأرسل إلى بقية السفن التي خرجت للغزو أو التي كانت في عرض البحر أن تتوجه إلى ميناء جيجل بدلًا من ميناء الجزائر، ويذكر أن أهالي المدينة تدفقوا إلى المرسى بعد أن علموا بمغادرتهم للجزائر، وأرسلوا وفدًا كبيرًا من العلماء إلى سفينته طالبين منه صرف النظر عن فكرة الرحيل من مدينة الجزائر إلى جيجل إلا أنه اعتذر لهم، وذكر أيضًا أن أحمد بن القاضي قد أصيب بالذعر فكتب إليه يعتذر عن عصيانه إلا أنه لم يقبل اعتذاره وانطلق في طريقه. وصل إلى جيجل -التي كانت أول قلعة يفتحها هو وأخوه عروج- بعد رحلة دامت يومًا كاملًا، ويذكر أن أهالي المدينة أقاموا احتفالًا كبيرًا عندما علموا بقدومهم، لأن الثروات التي كانت تتدفق على مدينة الجزائر سوف تتدفق على جيجل، وفي اليوم التالي وصل إلى جيجل شيوخ القبائل وأعيانها من الجزائر وحتى من تونس وأعلنوا خضوعهم للعثمانيين. ودفعوا الخراج السنوي وأعلموا خير الدين بأنهم حاضرون لإمداده بما يحتاج من رجال.
لم يطل خير الدين وبحارته المكوث في جيجل بل عجلوا بالخروج إلى الغزو في البحر، فوصلوا بقيادة خير الدين إلى سواحل صقلية وقصفوا عاصمتها بلرم، واستولوا خلال ذلك على تسع قطع بحرية كانت تحتوي على أربعين مخزنًا مشحونًا بالقمح وزيت الزيتون والخبز الجاف والألواح والفول والرز والقهوة والقماش والرصاص. وأقام في جيجل عددًا من الثكنات والمنازل، وقام ببيع ستة وثلاثين ألف كيل من القمح بأسعار رخيصة للخبازين. كما قام ببناء مصنع صغير لبناء السفن. وفي نفس الصيف أرسل سفنه للغزو هناك مرة أخرى. فتوجهت إلى خليج البندقية واستولت هناك على ثلاث سفن تحمل كلٌا منها عشرة آلاف دوقة ذهبية، بالإضافة إلى المئات من الأسرى، كان من بينهم ستون أسيرًا مسلمًا أمر بإطلاق سراحهم فورًا. وقد دامت هذه الغزوة ثلاثة وعشرين يومًا، وفي اليوم الرابع والعشرين رست السفن بمرسى جيجل فأمر بتوزيع حمولة إحدى السفن على الفقراء وبيع حمولة السفن الباقية، وقام بتوزيع حصص البحارة عليهم. وخرج للغزو في الربيع القادم في خمس عشرة قطعة بحرية، فدخل أولًا خليج جنوة ومكث هناك أربعة عشر يومًا يُغير على سواحلها، واستولى خلال تلك الفترة على واحد وعشرين سفينة أمر بإرسالها جميعًا إلى جيجل. وتجاوز بعد ذلك "مضيق ماسينا" ودخل خليج البندقية والتقى هناك بسفن صديقه "سنان ريس" الذي رجع معه إلى جيجل وفي طريقهم استولوا على تسع قطع بحرية.
تذكر بعض المراجع سبب ذهاب خير الدين من مدينة الجزائر إلى جيجل بروايات تختلف عن التي ذكرها في مذكراته، فيذكر المؤرخ "ابن أبي الضياف" في كتابه "إتحاف أهل الزمان بأخبار ملوك تونس وعهد الأمان" أن السلطان الحفصي محمد بن الحسن قد دخلته الغيرة من خير الدين بعد انتصاره في معركته الأخيرة ضد الإسبان، واشتد حذره منه وتحقق أنه إذا وصل يده بالدولة العثمانية سهل عليه الاستيلاء على المملكة التونسية، وندم على إضاعة الحزم، فركب متن الفساد والفتنة بين نواب خير الدين، وكاتب صاحب تلمسان يحذره من عائلة خير الدين. ويذكر المؤرخ "أحمد توفيق المدني" بعد أن اقتبس قول ابن أبي الضياف السالف ذكره أن خير الدين قد قسم مملكته في الجزائر إلى قسمين، قسم شرقي يشم البلاد القبائلية الجبلية، من شرقي العاصمة الجزائرية إلى حدود المملكة الحفصية التونسية ووضع على رأس هذا القسم أحمد بن القاضي سلطان كوكو وقد وصفه بأنه صديقه ورفيقه في الجهاد على عكس ما يذكر خير الدين من العداوة التي بينهما. أما القسم الغربي وهو الممتد من الجزائر إلى حدود الدولة الزيانية ووضع عليها "السيد محمد بن علي"، وظن خير الدين أنه يستطيع أن يعتمد على الزعيمين المحليين لحكم البلاد مباشرة بيد أبنائها، تاركًا لمدينة الجزائر السلطة العليا ومباشرة أمور الحرب والسياسة. إلا أن الأمراء المحليين والإسبان كانوا له بالمرصاد. فقد كان ملك قلعة بني عباس "عبد العزيز" عدوًا لدودًا لأحمد بن القاضي، وقد جعله النظام الإداري الجديد تحت إمرته، فكان يحمل لواء العصيان، ويعلن الطاعة والولاء للملك الحفصي بتونس. لكن الحالة تغيرت بصفة فجائية، فقد أعلن أحمد بن القاضي الثورة والانفصال عن دولة خير الدين بعد أن أساءت الدسائس العلاقات بينه وبين خير الدين، وانصاع لمساعي الدولة الحفصية معتمدًا على مددها ورجالها، فما ويع خير الدين إلا إخراج رجاله ومقاتلة ابن القاضي قتالًا مريرًا في جبال زواوة، واضطره للالتجاء إلى عنابة، ثم تلقى ابن القاضي مددًا من السلطان الحفصي التونسي، فعاد إلى الحرب واستفزاز سكان الجبال ضد حكم خير الدين، وساءت الحالة إلى أن قرر خير الدين الخروج بنفسه لمقاتلة صديقه القديم المنشق. وقد ذكر المؤرخ الفرنسي "دي قرامون" أن سلطان تونس قد عزم على إخضاع الجزائر تحت سلطته لأنها كانت نظريًا تابعة لدولة بني حفص، وتآمر مع ابن القاضي على أن يلتحق به أثناء اختراقه البلاد القبائلية، وأن يجتمعا على مقاتلة الجزائريين أصحاب خير الدين. خرج خير الدين وهو يعتقد أنه سيرد غارة الحفصيين معتمدًا على جيش الأتراك وجيش ابن القاضي، وما كادت المعركة تلتحم في "فليسة أم الليل" حتى أدار جنود ابن القاضي سلاحهم ضد خير الدين والأتراك فوقعوا بين نارين، وقتلوا عن آخرهم تقريبًا، ونجى خير الدين بنفسه وبعض رجاله إلى جيجل وأرسل يطلب من الجزائر سلاحه وأسطوله وكنوزه، ويكمل المؤرخ الفرنسي فيقول أن أحمد بن القاضي استمر يتقدم في متيجة ويخرجها، ودخل الجزائر فسلك فيها سيرة أدهى وأمر من سيرة الأتراك.
ويذكر المؤرخ "عزيز سامح التر" أن الأتراك بعد تمركزهم في الجزائر قد أحسوا أن الخطر سيأتي عليهم من تونس وتلمسان لذلك بدأ خير الدين يخطط لإخضاعهم تحت سيطرته، وبما أن الجزائر كان قديمًا مرتبطة بتونس فقد اعتبر السلطان التونسي أن خير الدين شخص عاص ومغتصب فبدأ هو الآخر لإعادة الجزائر إلى دائرة نفوضه وطرد خير الدين منها. ويذكر التر أن صفاء قلب خير الدين قد دفعه إلى تسليم نصف البلاد إلى أحمد بن القاضي معتقدًا أن ذلك سوف يساعد على استقرر الأمور واستتاب الأمن، لكن أحمد بن القاضي كان يكن الحقد والبغضاء لخير الدين فاتفق مع حاكم تونس وجمع القبائل حوله وحرضهم ضده، وحينما اطمأن إلى تأييدهم له، جهزهم بالسلاح، وتحرك حسب الاتفاق مع الجيش التونسي باتجاه الجزائر. وأعلنت القبائل المجاورة لمدينة الجزائر تمردها، فاضطر خير الدين إلى تأديبها، وقد استمرت عملية التأديب قرابة ستة أشهر، وقام أحمد بن القاضي بتأجيل عملية الهجوم بسبب حلول فصل الشتاء، وأجرى صلحًا مع خير الدين ثم توجه إلى تونس، فاستغل أخوه فرصة غيابه وعقد تحالفًا مع الجزائر بعدما أخبر خير الدين بالاتفاق الذي عقد أخوه أحمد بن القاضي مع حاكم تونس. وأعلن أحمد بن القاضي عن تحالفه مع خير الدين، فجهز قواته وانضم إليه، وحينما كان خير الدين يحارب القوات التونسية، انقلب أحمد بن القاضي وجنوده على خير الدين وجنوده، فوجد خير الدين نفسه بين نارين، وألحق به من جراء هذا التآمر خسائر فادحة، ولم ينج إلا هو وقليل من رجاله. وإثر الهزيمة التي لحقت بخير الدين فقد نفوذه خارج مدينة الجزائر، وكذلك فقد أعلن الجزائريون التمرد على الأتراك إلا أنهم لم يقوموا بمهاجمة القلعة التي يتواجدون فيها، وبما أن علاقة الأتراك لم تكن حسنة مع المناطق المجاورة فقد بقوا بدون المستلزمات المهمة، وأصبح خير الدين شبه محاصر، وبعد تفكير طويل قرر ترك المدينة والرحيل منها، ولكنه تخوف من مهاجمة أعداءه له عند تنفيذ قراره وقيامهم بمحاولة منعه من أخذ أمواله وعائلته، فتظاهر بتسليم البلاد لقره حسن وكلفه بإدارتها، وبحركة جماعية أخلى القصر، وحمل أمواله وأمتعته على متن تسع سفن، ثم نادى الأشراف والأعيان وألقى بمفاتيح القلعة لهم وقال: "ليكن أهالي الإسلام وديارهم أمانة في أعناقكم"، ثم ركب سفينته وتوجه إلى جيجل. وقد ذكر المؤرخ الجزائري "مبارك الميلي" نفس رواية التر.
كان انسحاب خير الدين من مدينة الجزائر إلى مدينة جيجل في سنة 927هـ/1520م، وبعد ذلك دخل أحمد بن القاضي الجزائر مع جنوده، ويذكر المؤرخون أنه ارتكب مظالم كبيرة بحق السكان، فغدا سكان الجزائر أكثر حبًا وتقربًا للأتراك، بالإضافة إلى أنه اختل النظام الأمني الذي كان قائمًا بوجود الأتراك وتدهورت الأوضاع في المدينة فتضاعفت نتيجة لذلك مشاعر التذمر من ابن القاضي. وفي فترة انسحابه عمل خير الدين على استعادة قوته القديمة بالرغم من أن الدولة العثمانية لم تقدم له خلال هذه الفترة الحرجة أي مساعدات، وما فعله كان بفضل جهوده وحسن تصرفه وإدارته للأمور كما يذكر المؤرخون، فقام بتأسيس قوة عسكرية جيدة أحضر جنودها من المتطوعين الذين انضموا إليه من داخل البلاد. واتفق مع سلطان قلعة بني عباس الذي كان عدوًا لأحمد بن القاضي، وقد كانت الوفود من مدينة الجزائر تتوالى على خير الدين وتطلب منه العودة إلى الجزائر. وفي نهاية الأمر وبعد مرور خمس سنوات على خروج خير الدين من مدينة الجزائر تحرك بجيش يبلغ عدده اثني عشر ألف بحار منهم أربعة آلاف فارس وثمانية آلاف راجل وفي طريقه انضم إليه الآلاف من الفرسان في الأرياف المجاورة. عند اقتراب خير الدين من المدينة تعرض له بعض رجال أحمد بن القاضي واشتبكوا في معركة أسفرت عن مقتل ثمانمائة منهم. كان لدى ابن القاضي اثنا عشر ألف فارس وثمانية آلاف راجل، إلا أنه كان يشك في رغبتهم على التصدي لجيش خير الدين، وعلى الرغم من هذا حاول ابن القاضي في أن يتصدى لهم، فقام في إحدى الليالي بالإغارة على ثلاث معسكرات لجيش خير الدين فكانت النتيجة أنه فقد مائة وخمسة وثمانين من رجاله وسبعة وتسعين من خيوله بينما لم يقتل أحد من رجال خير الدين، وعند الصباح أعاد هجومه مرة أخرى إلا أن رجاله كانوا يفرون إلى أعالي الجبال كما يذكر خير الدين في مذكراته. ودام القتال على هذا الحال حتى قُتل "قرة حسن" -الذي كان أحد بحارة خير الدين وانضم لصف ابن القاضي- فلم يبق لابن القاضي أي مجال للنجاة. بعد ذلك قام أحد شيوخ العرب بقطع رأس ابن القاضي وأرسله لخير الدين. بمقتل قرة حسن وأحمد بن القاضي لم تبق حاجة للحرب لأن أبواب مدينة الجزائر وطرقها مفتوحة أمامه، فدخلها خير الدين بلا مقاومة.
بعد استقرار خير الدين في الجزائر تفرغ لحل الأوضاع الداخلية للبلاد وأصبح يعمل على استعادة نفوذه السابق. فقد انتهز سلطان تلمسان "الأمير عبد الله الزياني" -الذي أجلسه خير الدين على عرشها- فرصة خروج خير الدين من الجزائر ليقوم بإلغاء السكة التي كان يسكها باسم السلطان العثماني، ليقوم بضرب العملة باسمه. فكتب له خير الدين بعد استقراره في الجزائر بوجوب إعادة السكة إلى حالتها القديمة، وإرسال الضرائب المتأخرة إلى الجزائر، وقام بتهديده بالقتل إن لم يفعل ذلك. إلا أن السلطان "عبد الله الزياني" قام بتمزيق ورمي رسالة خير الدين عندما استلمها. فقرر على إثر ذلك أن يقوم بمساندة ابنه الأمير "محمد بن عبد الله الزياني" الذي كان قد خرج على أبيه رغبة في خلعه والجلوس على عرش تلمسان. فلجأ إلى الجبال في ألفي فارس. وقام خير الدين بإعداد جيش سار به إلى تلمسان، فلحق به في الطريق الأمير محمد وانضم إلى جيشه. وفي هذا الوقت كان السلطان "عبد الله الزياني" قد خرج من تلمسان وسار إليهم. فالتقوا في مازونة حيث اشتبكت قواتهم هناك. وتمكن جيش خير الدين من تشتيت قوات السلطان عبد الله وأسره. فأمر خير الدين بضرب عنقه على الفور. وألبس ابنه الخلعة السلطانية وأجلسه على عرش تلمسان. أمر خير الدين أربعمائة بحار بمرافقة السلطان الجديد إلى تلمسان. فقام الأخير فور وصوله بدفع الضرائب المتأخرة وسلمها للبحارة والذي قاموا بدورهم بإرسالها إلى الجزائر.
عند رجوع خير الدين إلى الجزائر قام بتقسيم أسطوله إلى وحدات صغيرة، وأرسلها للغزو تحت إمرة "سنان ريس". وقد عاد الأخير بست سفن تجر ست سفن أخرى غنمها في البحر، كان إحداها مشحونة بالبارود والرصاص والقذائف المدفعية، إضافة إلى ستين قذيفة من البرونز. أما السفينة الثانية فقد كانت مشحونة بالنفط والقطران والأعمدة والألواح. وأما الثالثة فكانت تحمل الزيتون، وزيت الزيتون والجبن والعسل. وأما الرابعة فكانت مشحونة بالسكر، بينما كان الاثنتين الأخريين تحملان الأموال. عاد الأسطول الأول إلى الجزائر مشحونًا بالغنائم أكثر من غيره من الأساطيل الأخرى. ولم تصب أي سفينة من السفن الخمسة والثلاثين بأي أذى.
بعد أن عاد خير الدين من جيجل ودخل مدينة الجزائر عمل مباشرة على إعادة الجزائر إلى وضعها السابق حينما كانت تحت حكمه، فبدأ أولًا بضرب المتمردين بشدة، ودأب خلال سنتي 932هـ - 933هـ/1526م - 1527م على ملاحقة العصاة، فألقى القبض على حكام تنس وشرشال وتم قتلهم، وفرض سيطرته من جديد على الساحل الممتد من جيجل حتى وهران. وفي سنة 1528م الموافقة لسنتي 934هـ-935هـ تمردت قسنطينة وتم قتل القائد الذي عينه خير الدين عليها، حتى كادت أن تسقط المدينة في يد المتمردين، فاضطر خير الدين في ذلك العام إلى توجيه ضربة قاسية على المدينة وعلى القبائل المجاورة لها، وغدت المنطقة وما جاورها خالية من السكان عدة شهور وأصبحت ماوى للوحوش والأشقياء. وبعد مقتل أحمد بن القاضي سلطان إمارة كوكو لم يعد يواجهه أي خطر أو اعتراض من أي جهة، ولم يعد يخشى أحدًا من جيرانه، إلا أن وجود الإسبان في حصن الصخرة (بنيون) كان يشكل تهديدًا عليه. فقد شيد الإسبان في سنة 916هـ الموافقة لسنة 1510م قلعة حصينة على أرض صخرية تدعى "البنيون" أي "حصن الصخرة" وتقع هذه القلعة في عرض البحر على مسافة ثلاثمائة متر من مرسى الجزائر. كان وجود الإسبان في هذه القلعة يشكل خطرًا كبيرًا ومباشرًا على مدينة الجزائر، وكان أهل الجزائر يعتبرون وجودهم في هذه القلعة إهانة كبيرة لهم، إضافة إلى أن السفن الجزائرية كانت تواجه عددًا من المصاعب في الذهاب والإياب. وقد كان الإسبان قبل قدوم الأخوة بربروس يمطرون مرسى الجزائر بقذائفهم، فيضطر أهالي المدينة إلى الخضوع لهم وقبول ما يملونه عليهم. وباستقرار خير الدين في الجزائر بصورة نهائية فقد أصبح طرد الإسبان من القلعة ضرورة حتمية لتعزيز سلطانه من جهة، ويضمن لسفنه ولميناء الجزائر الأمن والسلامة من جهة أخرى. فأرسل في سنة 935هـ/مايو 1529م خطابًا إلى قائد القلعة "دون مارتن دي فرغاس" يدعوه فيه بضرورة تسليم القلعة ومغادرتها مع جنوده فورًا دون أن يصيبهم أذى، إلا أن قائد القلعة رد عليه بالرفض. فشرع خير الدين بقصف القلعة لمدة عشرين يوم إلى أن تمكن من اقتحامها في 17 رمضان 935هـ/26 مايو 1529م، وبعد معركة كبيرة أعلن دون مارتن مع سبعمائة من رجاله استسلامهم. ويشير خير الدين في مذكراته أن الإسبان كانوا يقومون بقصف المآذن عندما يسمعون الأذان من باب التسلية، إلا أنهم توقفوا عن فعلهم هذا بعد استقرار الإخوة بربروس في الجزائر. وعندما استولى خير الدين على القلعة جيء إليه بقائد المدفعية الذي كان قد دمر العديد من المآذن وقتل كثيرًا من المؤذنين، فأمر بوضعه في فوهة مدفع وأمر بقذفه في البحر، وضرب عنق مساعده مع عشرة من جنود المدفعية، أما الباقون فقد أمر بإلقائهم في الزنازين. أمر خير الدين بتلغيم الصخرة وتفجيرها. وبعد ذلك جمع ثلاثين ألف أسير كانوا يقبعون في السجون فاستخدمهم في جمع صخور القلعة لبناء كاسر أمواج يربط بين القلعة والميناء. بعد سقوط القلعة بعشرة أيام قدمت إليها تسع سفن إسبانية محملة بالمؤونة والأسلحة والمعدات بناء على طلب قائد القلعة دون مارتن دي فرغاس، لكن قادة السفن لم يجدوا أي أثر للقلعة فأصيبوا بالدهشة، وعندما اقتربت السفن ولم تر القلعة ظنت أنها ضلت طريقها، وبينما هي تحاول معرفة طريقها إذا بخمس عشرة سفينة من سفن خير الدين تحيط بها من كل جانب، فتم القضاء على معظم السفن، بينما استسلم ثلاثمائة وخمسة وثلاثون منهم، حيث تم إرسالهم إلى السجن. وقد تركت هذه الحادثة انطباعًا بأن السفن الإسبانية لم يعد بإمكانها أن تقترب من سواحل الجزائر.
بعد فتح حصن الصخرة بفترة توجهت أنظار خير الدين نحو السواحل الإسبانية. فقام في سنة 936هـ/1529م أو 937هـ/1530م بإرسال كبير قباطنته "آيدين ريس" نحو الغزو في غرب البحر الأبيض المتوسط، وأمره بأن يتوغل في مضيق جبل طارق، وأن يقوم باحتلال سواحل إسبانيا دون أن يدع لهم فرصة للنيل منه. وأن يحمل في سفنه ما يقدر عليه من المسلمين اللاجئين إلى جبال غرناطة، ويأخذهم إلى الجزائر. فغادر آيدين ريس مرسى الجزائر في عشرة سفن وتوغل في غرب البحر الأبيض المتوسط حتى بلغ مضيق جبل طارق كما أمره خير الدين. فصادف في طريقه خمس قطع بحرية عملاقة من نوع "قادرغة". اشتبك مع بحارتها في معركة كبيرة انتهت باستيلائه عليها جميعًا، ثم قام بشحنها بالبحارة الأتراك وإرسالها إلى الجزائر. ومن جهة أخرى استمر آيدين ريس في الإغارة على المدن والبلدات المطلة على الساحل وقصفها بالمدافع، كما كان يحمل كل من يعثر عليه من المسلمين في سفنه، حتى لم يبق في سفنه موضع قدم فارغ.
عندما علم الملك الإسباني شارلكان بوجود آيدين ريس في السواحل الإسبانية أرسل أكبر أميرالاته المدعو "بورتوندو" (باللغة الإسبانية: Rodrigo de Portuondo) لكي يقطع طريق العودة على آيدين ريس، ووعده بمكافأة قدرها عشرة آلاف دوقة إن نجح في مهمته هذه. فقام بورتوندو باعتراض أسطول آيدين ريس بأسطول ضخم في أحد سواحل إسبانيا. فتشاور آيدين ريس مع صالح ريس -الذي كان أحد رؤساء البحر المرافقين له- في كيفية التصدي للأسطول الإسباني. فتوصلا إلى قناعة بأنه يجب عليهم أن ينزلوا المهاجرين الأندلسيين في الساحل، لكي يتمكنوا من القيام بإدارة المعركة بفعالية كبيرة، وعندما يفرغون من أمر الإسبان يرجعون إليهم ويحملونهم إلى الجزائر. وعندما علم الأندلسيون بهذا القرار أصيبوا بالهلع، وتعالت أصواتهم بالبكاء والنحيب، ورفضوا أن ينزلوا من السفن، وقد كان أكثرهم من النساء والأطفال. فاضطر آيدين ريس وصالح ريس إلى إجبارهم على النزول. واقتربت سفن الأميرال بورتوندو كثيرًا، فعاجلهم آيدين ريس وصالح ريس بهجوم مباغت وسريع. واشتبكا معهم في معركة شرسة انتهت بالاستيلاء على سبع سفن إسبانية عملاقة، وقتل بورتوندو وجميع من كان معه من القباطنة. تمكن آيدين ريس من تحقيق انتصار حاسم بمساعدة صالح ريس الذي اشتهر بدهائه المفرط، ومنذ هذه المعركة أطلق المسيحيون لقب "الشيطان الضارب" و"الكافر الضارب" على الأتراك. وإضافة إلى غنم السفن تم أسر ثلاثمائة وخمسة وسبعين إسباني، وأما بقية الجنود فقد تم القضاء عليهم جميعًا في المعركة. كما تم إنقاذ الأسرى المسلمين الذين كانوا مقيدين في المجاديف. أما الأندلسيون الذي تم إنزالهم من السفن فقد وقفوا يراقبون سير المعركة، حتى انتهت المعركة تم حملهم من جديد في السفن ونقلوا إلى الجزائر. خلال هذه الفترة توفي "سنان ريس"، فقام خير الدين بدعوة آيدين ريس بعد وفاته بأيام قلائل. وقام بتعيينه قائدًا للأسطول مكان سنان ريس. كما عين صالح ريس نائبًا له.
تنص المصادر أنه على إثر فتح قلعة بنون وهدمها وطرد الإسبان منها على يد خير الدين عم الغضب والهيجان في مختلف المناطق الإسبانية، فاندفع أهالي السواحل بشكل دائم ومستمر على المجلس العالي للدولة الإسبانية يشكون أوضاعهم، وما يعانونه من رعب وخوف من جراء مهاجمة خير الدين وبحارته عليهم، وطالبوا بإنقاذهم وتخليصهم منهم، وبناء على طلب الأهالي وإلحاحهم قرر المجلس غزو الجزائر وإرسال حملة إليه، ووافق الملك على القرار. وتنص مصادر أخرى أن الإسبان كانوا يريدون أن يضربوا الجزائر ضربة حاسمة بعد الهزيمة التي لحقتهم في مدينة الجزائر سنة 1519م وأن يجعلوا الساحل الجزائري بالكامل تحت سيطرتهم حيث أنهم في ذلك الوقت كانوا يسيطرون على شرقه بواسطة مركز بجاية، ويسيطرون على غربه بواسطة مركز وهران والمرسى الكبير.
قام الملك الإسباني شارلكان بتعيين القبطان الجنوي أندريا دوريا قائدًا لهذه الحملة، فأخذ الأخير يجمع أسطوله في مدينة جنوة واستمر تجهيز هذا الأسطول قرابة العام. وفي 938هـ/يوليو 1531م تحرك أندريا دوريا بأسطوله المكون من ثلاثين أو أربعين سفينة من جنوة باتجاه الساحل الجزائري. فقام بالإغارة ميناء شرشال الذي لم يكن يحرسه سوى بضع مئات من البحارة. وعندما رأى البحارة أسطول دوريا يقترب من الميناء قاموا بالتحصن في القلعة، ولما كان رجال دوريا منهمكين في نهب من وجدوه في المرسى والمدينة انتهز البحارة هذه الفصة وفتحو أبواب القلعة وقاموا بهجوم خاطف على رجال دوريا، وتفرق البحارة في أزقة وشوارع المدينة واستطاعوا أن يقتلوا المئات منهم مستفيدين من فرصة تفرقهم وعجزهم على الاجتماع في معسكر واحد. ولاذ الآخرون من رجال دوريا بالفرار إلى سفنهم، بينما وقع ألف وسبعمائة منهم في الأسر. عندما بلغ خير الدين هجوم دوريا على شرشال خرج إليه في أربعين قطعة، إلا أنه ما إن علم بخروجه حتى غادر شرشال ولم يدرك خير الدين سوى أسطول صغير تابع له تمكن من الاستيلاء عليه بعد معركة عنيفة. عندما كانت المعركة على أشدها قام الأسرى المسلمون المقيدون بالسلاسل في السفن الإسبانية بكسر أغلالهم. وانجلت المعركة عن مقتل أكثر من ثلاثمائة من رجال خير الدين. تمكن البحارة من الاستيلاء على الأسطول بأكمله فبلغ عدد سفن خير الدين ستين قطعة. وذهب بها جميعًا إلى مرسى شرشال. بلغ عدد الأسرى المسلمين الذي قام خير الدين بتحريرهم ألفين ومائتي أسير أطلق سراحهم جميعًا. فاختار قسم منهم أن يدخل في خدمة خير الدين، بينما أعطى الآخرين ما يحتاجون إليه من مال وأرسلهم إلى بلادهم. وأما عدد الأسرى من سفن دوريا فقد بلغ ألفًا وتسعمائة أسير من بينهم أسير من الإفرنج برتبة "أميرال" كما كان من بينهم قبطان كبير آخر. وأمر خير الدين بربطهم جميعًا بمجادف السفن لكي يعملوا في دفعها خلال أسرهم. ولم خير الدين يمكث في شرشال سوى بضع ساعات قبل أن يغادرها متوجهًا إلى الجزائر.
يشير خير الدين في مذكراته أنه كان يريد أسر أندريا دوريا، ولتحقيق ذلك جعل "آيدين ريس" على رأس أسطول كبير وأمره بتعقبه. فخرج آيدين ريس بأسطوله حتى بلغ سبتة، وتوعل في سواحل الإسبان إلى أتى جبل طارق، ومن هناك عبره إلى المحيط الأطلسي، إلا أنه لم يقف على أثره. فقفل راجعًا إلى الجزائر، وأغار في أثناء عودته على جزر البليار وقصف جزيرة ميورقة والسواحل الإسبانية المطلة على البحر الأبيض المتوسط. فتمكن بهذه الحملات من أسر ثلاثة آلاف حملهم جميعًا في سفنه. وتوغل في في الأراضي الإسبانية حتى كان على مقربة من ميناء برشلونة. وعلى مسافة قريبة منها كان يوجد دير كبير تعود ملوك إسبانيا على زيارته في كل سنة، فقام آيدين ريس بالإغارة عليه وأسر ثمانين راهبًا واستولى على ستة وثلاثين صندوقًا من خزائن الدير. يشير خير الدين أن هذه الهجوم كان يمثل ضربة قاضية لكبرياء الملك شارلكان. فقد بلغ عدد السفن التي استولى عليها آيدين ريس خمسًا وخمسين قطعة ما بين سفينة كبيرة وأخرى صغيرة، قام بسحبها جميعًا ودخل بها ميناء الجزائر. وبهذه الهجمات يكون خير الدين قد أعطى رده لأندريا دوريا بعد غارته التي شنها على شرشال.
بلغ عدد الأسرى المحبوسين في الزنازين في الجزائر ستة عشر ألف أسير عدا الذين تم تكليفهم بالجدف في السفن أو الذين تم تخصيصهم للخدمة في البيوت. قام خير الدين باختيار خمسمائة أسير من الجدافين وأرسلهم إلى عاصمة الدولة العثمانية إسطنبول لكي يعملوا في الأسطول العثماني، وندب لهذه المهمة آيدين ريس الذي قام بنقلهم في خمس عشرة سفينة. وصل آيدين ريس إلى إسطنبول ومثل بين يدي السلطان سليمان القانوني وقام بقراءة رسالة خير الدين بنفسه. وقام آيدين ريس بزيارة الوزراء وغيرهم من أركان الدولة فحظي منهم بتقدير وإكرام كبيرين. وطلب السلطان سليمان آيدين ريس للمثول بين يديه مرة أخرى، وأخبره بقبول جميع الأعمال التي يقوم بها خير الدين بصفته بكلربك على الجزائر. وأرسل معه خمس قطع بحرية مليئة بالمستلزمات الحربية من قذائف وآلات الحرب. وأرسل أيضًا عددًا من مهندسي المدافع. وأنطلق آيدين ريس إلى الجزائر وفي طريقه أستولى على سبع سفن أغار بها جميعًا على عدد من المدن فتمكن خلال غزواته تلك من أسر سبعمائة أسير. في هذه الأثناء كان الملك الإسباني شارلكان منشغلًا عن الجزائر بعد أن أرسل إليه أخوه الملك فرديناند الأول من فيينا يطلب المدد منه، فقام شارلكان بتحريض سلطان تلمسان على الثورة على خير الدين مرسلًا إليه أموالًا كثيرة ووعده بجعله سلطانًا على الجزائر. وقد كان سلطان تلمسان يعتبر نفسه السلطان الشرعي على الجزائر ولذلك استجاب لشارلكان وراح يوزع وعوده على المحيطين به، وأعلن عصيانه على خير الدين، عند ذلك أمر خير الدين "دلي محمد ريس" بأن يخرج للغزو في البحر بينما ذهب هو بنفسه إلى تلمسان، وعندما وصل إليها لم يجد سوى مقاومة صغيرة لاذ بعدها سلطان تلمسان بالفرار، وأرسل بعد ذلك العلماء يطلب العفو. فوافق خير الدين على ذلك بشرط أن يأتي بنفسه ويعتذر منه. فجاء إليه واعتذر منه ودفع الخراج المتأخر. وعندما كان خير الدين في تلمسان صادف "دلي محمد ريس" بأسطوله المكون من أربعين قطعة أسطولًا إسبانيًا مكونًا من خمس وثلاثين سفينة، وسرعان ما اشتبك معها في عرض البحر، وما إن حمي الوطيس حتى أعلنت تسع وعشرين سفينة إسبانية استسلامها له، بينما لاذت الستة سفن الباقية بالفرار.
يشير خير الدين في مذكراته أن مسلمي الأندلس قد قويت قلوبهم بعدما بلغتهم انتصارات المسلمين في الجزائر، فنزل ثمانون ألفًا ممن كانوا معتصمين بالجبال فألحقوا بهم هزائم كبيرة. وما إن وصلت أخبار الثورة لخير الدين حتى أمر محمد ريس بالخروج على رأس أسطول مكون من ست وثلاثين سفينة لنصرة الثائرين. فشرع محمد ريس على الفور في إمداد الثوار في السواحل الإسبانية. هذا؛ وقد بلغت عدد حملات أسطول خير الدين على الإسبان واحد وعشرين حملة، في كل منها كان يقوم بإنقاذ آلاف المسلمين الأندلسيين من محاكم التفتيش الإسبانية، ونقلهم إلى سواحل شمال إفريقيا. وقد كان خير الدين يتولى قيادة الأسطول في معظم هذه الحملات بنفسه، كما تولى "آيدين ريس" و"سنان ريس" قيادة الأسطول مرات عديدة.
في سنة 939هـ/1533 وجه السلطان سليمان القانوني فرمانًا سلطانيًا إلى خير الدين أمره فيه بالقدوم إليه في إسطنبول بعد أن يستخلف أحدًا يعتمد عليه في الجزائر. شرع خير الدين بعد تلقيه الخبر يتأهب للسفر، وتنص المصادر على أن الإمبراطور الإسباني شارلكان أمر قائده الجنوي أندريا دوريا بقطع طريقه والحيلولة دون خروجه، فحاول الأخير ذلك إلا أنه فشل في مسعاه. خرج خير الدين أخيرًا من الجزائر في أسطول كبير مكون من ست وعشرين سفينة قادرغة متوجهًا إلى إسطنبول، بينما ترك بقية القطع الأخرى في الجزائر وغرب البحر الأبيض المتوسط. (وقد استخلف ابنه المعنوي حسن آغا على الجزائر). وفي طريقه كان خير الدين يغير على السواحل الجنوبية لإيطاليا التي كانت تابعة للإسبان الغربية، وعلى السواحل الغربية لجزيرة سردينيا ثم توغل شمالًا حتى بلغ مشارف جنوة، وقد كان سبب إغارته على هذه السواحل أن الدولة العثمانية كانت في حرب مفتوحة مع الإسبان ولكي يتوج خير الدين دخوله إلى إسطنبول بالنصر والغنائم. ومن هناك واصل طريقه محاذيًا سواحل إيطاليا حتى دخل ميناء مسينا فوجد أسطولًا إسبانيًا مكونًا من ثمان عشرة قطعة استولى عليه جميعًا وقام بربطها بسفنه بعد معركة عنيفة في عرض البحر. أما أندريا دوريا فقد كان يجوب سواحل المورة وعندما بلغه انتصار خير الدين في مسينا هرب إلى أيونيا فتعقبه خير الدين إلا أنه لم يتمكن من إدراكه، فأرسل خلفه خمسًا وعشرين سفينة لمطاردته فصادفت في طريقها أسطولًا صغيرًا لدوريا مكونًا من سبع قطع، استسلمت اثنتان منها بعد الاشتباك معها بينما لاذت خمس بالفرار. أما خير الدين فقد خرج من جزر أيونيا متجهًا نحو الجنوب فقدم إلى سواحل جزيرة المورة، وفي هذا الوقت كان "كامنكاش أحمد باشا" قبطان داريا الأسطول العثماني راسيًا بقسم من الأسطول العثماني في ميناء نافارين الواقع جنوب غرب جزيرة المورة. فتوجها معًا نحو إسطنبول. بعد وصول خير الدين إلى إسطنبول قام باستعراض كبير أمام أهالي المدينة، ونزل في قصر أحمد باشا مع ثماني عشرة ريسًا من رياس البحر المشاهير، وفي اليوم التالي دعي مع بحارته بالمثول في مجلس الديوان السلطان أمام السلطان سليمان القانوني وقد قام الأخير بالمبالغة في الثناء عليهم.
قام السلطان سليمان القانوني بتعيين خير الدين في منصب قبطان داريا على الأسطول العثماني أي أميرًا على الأسطول العثماني، واستبقاه على منصبه في إيالة الجزائر بصفته «بكلربك» عليها (أي أميرًا على أمرائها)، إلا أنه طلب منه أن يختار من يراه مناسبًا لإدارتها نيابة عنه والإشراف عليها باسمه. بعد أن انتهى خير الدين من اجتماعه مع السلطان سليمان أمره بالذهاب إلى حلب ليلتقي بالصدر الأعظم إبراهيم باشا ليتبحاث معه بخصوص الأمور المتعلقة بالمنصبين، وعند وصوله إلى حلب مكث فيها يومين ناقش فيها مع الصدر الأعظم الأوضاع السياسية في أوروبا والعمليات البحرية التي يقوم بها الأسطول العثماني، وعند فراغهم أصدر إبراهيم باشا فرمانًا بتعيين خير الدين في منصب قبطان داريا وألبسه الخلعة، وقد كان ذلك في 4 أبريل 1534م الموافق 21 رمضان 940هـ.
خرج خير الدين من حلب متوجهًا إلى إسطنبول، وبعد وصوله لها بدأ بممارسة عمله كقبطان للأسطول العثماني. وبتعيينه في هذا المنصب أصبح عضوًا في الديوان الهمايوني (ديوان السلطان). أعطى السلطان سليمان لخير الدين صلاحيات واسعة فيما يتعلق بصناعة السفن وتنظيم الأسطول -تنص المصادر على أن خير الدين أصبح أقرب مستشاري السلطان سليمان بعد أن تولى قيادة الأسطول العثماني-، فبدأ خير الدين معتمدًا على خبرته السابقة بذلك، فوضع في ورشة بناء السفن في إسطنبول 61 هيكل سفينة في مدة قصيرة. ساند السلطان سليمان القانوني بسياسته البحرية خير الدين بشكل كبير، وتتلخص هذه السياسة في تعزيز الأسطول الهمايوني بحيث يكون أقوى من مجموع بقية الأساطيل، ومع احتمال تعذر ذلك من حيث عدد السفن، فقد تعهد بربروس بإمكان تحقيق ذلك من حيث تأمين تفوق مرمى المدافع وتربية وتدريب الأفراد، وتقرر استبدال السفن والمدافع وتجديدها خلال بضع سنوات وبيع القديم منها إلى الداخل والخارج، وتجهيز السفن بصورة متفوقة.
خرج خير الدين للغزو لأول مرة بصفته أميرًا على الأسطول العثماني في سنة 940هـ/1534م في ثمانين سفينة من وحدات الأسطول، متجهًا نحو السواحل الإيطالية حتى بلغ مضيق مسينا، فوصل لمدينة ريدجو المطلة على مسينا وقام بمهاجمتها وتدميرها، ثم استولى على قلعة "سانت أوسيدو" ثم أحرقها، ثم هاجم مدينة سان لوكا التابعة لريدجو ودمرها هي الأخرى. وانتقل بعدها إلى مهاجمة مدينة ، وأحرق 18 سفينة مسيحية كانت راسية في ميناء تلك المدينة. ثم اتجه في طريقه نحو سواحل نابولي فاستولى على قلعتها وأسر من فيها، أعقب ذلك وصوله إلى منطقة التابعة لنابولي وتم تدميرها، كما هاجم قلاع وقام بتدميرها، وغيرهن من المدن والقلاع. تمكن خير الدين في هذه الحملة من حمل ستة عشر ألف أسير، وفتح ثمان عشرة قلعة، فقام بإرسال مفاتيحها مع ستة عشر ألف أسير، وأربعمائة وخمسة وعشريم صندوقًا كبيرًا من الغنائم على متن أربعين سفينة إلى إسطنبول، واحتفظ لنفسه بأربعين سفينة ليكمل بها مسيره. بعد أن فرغ خير الدين من تلك المناطق اتجه إلى سردينيا فقام بمهاجمتها وأنزل جنوده فيها، وبعد أن أثقلت سفنه بالغنائم والأسرى توجه إلى الجزائر، وبسبب سوء الطقس توجه إلى بنزرت التونسية، وما أن شاهد حاكم بنزرت ضخامة أسطول خير الدين حتى أسرع إلى السلطان الحفصي يخبره بذلك. تنص المصادر على أن خير الدين قصد من ضرب السواحل الأوروبية وتدميرها نشر الرعب في نفوس الأوروبيين، وتمهيدًا للهجوم على تونس، فإن الأمر يتطلب منه صرف أنظارهم عن مهاجمة تونس، وبعمله أجبر الحكومات الأوروبية على توزيع قواتها ضمن أراضيها وبصورة خاصة على سواحلها بهدف التصدي لخير الدين في حال مهاجمته تلك المناطق مجددًا، وتنص بعضها الأخرى على أن القصد منها استدراج أندريا دوريا ومنازلته، إلا أن الأخير لم يصدر أي ردة فعل.
كان خط مسير الأسطول العثماني بقيادة خير الدين بربروس بعد حملته على السواحل الإيطالية أن توجه إلى الجزائر وبسبب سوء حالة الطقس توجه إلى بنزرت التونسية، التي خرج منها متوجهًا نحو مدينة تونس عاصمة الحفصيين، وما أن وصل المدينة حتى خرج الأهالي لاستقباله، فسمع بذلك السلطان الحفصي أبو عبد الله الحسن، وفي نفس الوقت استطاع خير الدين دخول حلق الوادي، وأنزل قواته إلى البر، ودخل تونس بخمسة آلاف خيال، وتمكنت قواته من الاستيلاء على القلعة، وينص في مذكراته أنه بعد دخوله لمدينة تونس فتح سائر نواحي السلطنة حتى بلغ القيروان في الجنوب ثم قفل راجعًا إلى تونس، وفي 6 صفر 941هـ/16 أغسطس 1534م هرب السلطان الحفصي الحسن من تونس، أما أنصاره الذين رغبوا بالمقاومة فأُلقي القبض عليهم، ووضعوا في القلعة في حين قتل بعض الشيوخ ممن وضعوا ترتيبات المقاومة. استنجد السلطان الحفصي بالإمبراطور الإسباني شارلكان لاستعادة عرشه، فلبى الأخير الدعوة، وعلم خير الدين أنه سوف يتوجه إلى تونس ليخرجه منها، لأجل ذلك شرع خير الدين على الفور في الاستعداد للتصدي له. في شتاء ذلك العام أرسل خير الدين بعض سفنه لضرب السواحل الإسبانية في غرب البحر المتوسط، وكان قد وجه أسطوله للإغارة على سواحل سردينيا فعاد محملًا باثنتي عشرة ألف دوقة ذهبية، وأربعمائة وخمسة وسبعين أسيرًا بالإضافة إلى غنائم أخرى.
خرج شارلكان من ميناء برشلونة في 1 ذو الحجة 941هـ/2 يونيو 1535م بجيش قوامه عشرين ألف من المشاة وألفين من الخيالة وقد تم حشد هؤلاء الجنود من الممالك الخاضعة تحت سيطرته مثل إيطاليا وألمانيا وهولندا وأسبانيا وغيرها، إضافة إلى فرسان مالطة، ومعه عدد كبير من المدافع، تنص بعض المصادر أن عدد سفن أسطوله كان مكونة من مئتي سفينة، بينما يذكر خير الدين في مذكراته أن عدد سفن أسطول شارلكان كان خمسمائة قطعة بحرية بين قطع حربية وبين سفن لنقل الجنود. وصل شارلكان إلى تونس بعد سبعة عشر يومًا من مغادرته ميناء برشلونة، وكان الاستيلاء على تونس يستلزم احتلال قلعة حلق الوادي، ولمنع الإسبان من تحقيق ذلك كلف خير الدين "سنان ريس" بالدفاع عن القلعة وزوده بعدد كاف من الجنود. أمر شارلكان بادئ الأمر بمحاصرة القلعة، وحالما اقتربت سفينته، أمر الغاليات الأربع المرافقة له بقصف القلعة بشكل مستمر، ثم أنزل جيشه إلى البر بمدافعه الثقيلة. باشر جيش شارلكان بالهجوم مع قصف مدفعي، وعلى الرغم من القصف المستمر فقد ظلت قلعة حلق الوادي صامدة مدة شهر كامل، وخلال القصف الكثيف نظم سنان ريس ثلاث هجمات خاطفة على قوات الإسبان تم خلالها قتل ستة آلاف جندي من قواتهم.
أما خير الدين فقد كان في تونس يتربص لما سوف يقوم به سلطان تونس الحسن، وكان مع خير الدين اثني عشر ألف جندي نصفهم من المتطوعين البدو، وكان يريد الصمود لأطول مدة ممكنة في حلق الوادي، لأنه كان قد أرسل إلى إسطنبول أوامره بضرورة التعجيل بإرسال الأسطول العثماني إلى تونس، فإذا وصل الأسطول فإن شارلكان سوف يجد نفسه بين نارين، إلا أن شارلكان كان يعلم هذا أيضًا، ولذلك كان يستعجل في احتلال حلق الوادي متغاضيًا عن خسائره الكبيرة. أما السلطان الحفصي الحسن فقد كان في طريقه إلى تونس في ألف وستمائة فارس، وثمانية آلاف جمل محمل بالطعام ولوازم الحرب.
لما بدت علامات سقوط قلعة حلق الوادي بيد الإسبان ظهرت أمارات التذمر والثورة في تونس، فانقلب عليه المتطوعون البدو الذين كانوا تحت إمرته ويبلغ عددهم ستة آلاف رجل، فقام هؤلاء بينما كان خير الدين معسكرًا برجاله الستة آلاف الآخرين أمام أسوار المدينة بفتح أبواب سجون المدينة لينطلق منها عشرة آلاف أسير نصراني كانوا فيها، ويشير خير الدين في مذكراته أن خيانة كثير منهم له كانت نتيجة الدعاية التي أطلقها السلطان الحفصي عبر جواسيسه الذين كانوا يشيعون بين الناس أن السلطان الحفصي الحسن قد اتفق مع الإمبراطور الإسباني شارلكان، وأنهم قد جاؤوا لإنقاذ تونس من الأتراك، وأنهم لن يريقوا قطرة دم مسلم عندما يدخلون المدينة. وبهذا الوضع وجد خير الدين وجيشه أنفسهم في وسط محيط معادي له، فمن جهة كان عليهم أن يتصدوا لعشرة آلاف أسير الذي استولوا على المدينة من داخلها، وفي ذات الوقت كان عليهم أن يقاتلوا جيش شارلكان. وفي هذه الأثناء سقطت قلعة حلق الوادي، إلا أن سنان ريس تمكن من الانسحاب بكفاءة عالية إلى مدينة تونس في 14 محرم 942هـ/14 يوليو 1535م بمن بقي معه من البحارة الأتراك لينضم لخير الدين. بالرغم من ذلك بقي خير الدين يدافع عن تونس ستة أيام بعد سقوط قلعة حلق الوادي، وكبد جيش شارلكان خسائر كبيرة.
بالتحاق البحارة الذين جاء بهم سنان ريس من قلعة حلق الوادي ارتفع عدد قواته إلى تسعة آلاف وسبعمائة جندي. وفي المقابل كان الجيش الإسباني مكونًا من ثلاثين ألف جندي وخمسمائة سفينة مجهزة بمئات المدافع، يسانده السلطان الحفصي الحسن الذي سار نحو تونس في جيشه من الجنوب، جعل هذا كله التصدي لهذه القوات في حكم المستحيل. وزيادة على ذلك فإن أربعين مدفعًا كبيرة من ذخيرة خير الدين قد استولى عليها الإسبان في حلق الوادي.
ذهب الحسن الحفصي إلى معسكر شارلكان وتنص الكثير من المصادر أن الحسن قد خر على قدميه أمامه وقبل رجليه، وبفضله شرع في حشد قوات كبيرة من لمحاربة خير الدين. في أول اشتباك لخير الدين مع الإسبان وحليفهم الحسن الحفصي فقد ألفين وخمسمائة جندي. وكانت مؤشرات الحرب توحي بأنه ليس في وسعه الاستمرار في المعركة بمن بقي معه من الجنود البالغ عددهم سبعة آلاف ومائتي جندي، بالإضافة إلى شدة حرارة الجو حيث كان وقت المعركة في وسط فصل الصيف. بعد قيام خير الدين بآخر حملة على الجيوش المعادية، أراد الانسحاب إلى المدينة، إلا أنه فوجئ بإغلاق الأهالي أبواب المدينة في وجهه، وكان ذلك بعد أن قام أسير نصراني وتحول إلى الإسلام يدعى جعفر بفتح أبواب السجن فاندفع الأسرى النصارى من زنازينهم وتفرقوا في أنحاء المدينة حتى تمكنوا من السيطرة عليها. قام خير الدين أخيرًا بهجوم كبير بهدف تشتيت صفوف جيش شارلكان ومن معه، وفي هذه المعركة سقط الآلاف من جنود خير الدين، ونجا بنفسه ولم يبق معه سوى آيدين ريس وسنان ريس وبضعة آلاف من البحارة المثخنين بالجراح. وبعدما استطاع البحارة تمزيق صفوف الجيش المقابل، قطعوا بقيادة خير الدين خليج تونس من بدايته إلى نهايته حتى بلغوا عنابة حيث كانت تنتظرهم أربع عشرة سفينة حربية، وفي هذه الأثناء غرق آيدين ريس وتوفي. عندما اقتحم الصليبيون تونس قاموا بذبح ثلاثين ألف مسلم عربي، واسترقاق عشرة آلاف امرأة وطفل، وخربوا المساجد والمدارس والمقابر ونهبوا محتويات القصور، كما قاموا بحرق آلاف المخطوطات والكتب.
بانسحاب خير الدين من تونس سقطت المدينة وضواحيها بيد شارلكان، وخضع الحفصيون للإسبان، بينما بقيت المناطق الجنوبية جميع السواحل الشرقية خاضعة لحكم خير الدين، أما تونس فكانت قد بقيت تحت إدارته أحد عشر شهرًا. خرج خير الدين من عنابة إلى الجزائر، ومن هناك خرج في اثنتين وثلاثين قطعة بحرية حتى بلغ جزر البليار حيث أمر بنهب جزيرتي ميورقة ومنورقة، وتمكن من أسر خمسة آلاف وخمسمائة أسير من ميناء ماهون وبالما. بعد ذلك توغل في المحيط الأطلسي عبر مضيق سبتة وطاف بأسطوله في خليج كديز الواقع بين إسبانيا والبرتغال حيث قام بتخريب ميناء فارو جنوب البرتغال. واستولى في سواحل فارو على سفينة كبيرة من سفن البرتغال، كانت مجهزة بستة وسبعن مدفعًا، وعلى متنها ثلاثمائة بحارة، ويدفعها مئات الجدافين، وكانت السفينة قادمة من الهند محملة ببضائع هندية قيمة، بالإضافة إلى ستة وثلاثين ألف دينار ذهبي فقام بسحبها إلى الجزائر. وبعد أن أقام فيها مدة قصيرة توجه إلى إسطنبول في 13 ربيع الآخر 942هـ/10 أكتوبر 1535م وذلك بعد أن عين ابنه المعنوي حسن آغا وكيلًا له على الجزائر. وبخروج خير الدين من الجزائر هذه المرة أصبحت حياته غير مرتبطة بالشمال الإفريقي، بل أصبحت مرتبطة بالتاريخ العثماني.
خرج خير الدين من الجزائر في 13 ربيع الآخر 942هـ/10 أكتوبر 1535م متوجهًا إلى إسطنبول بعد أن خسر تونس لصالح الإسبان، وكانت قد بقيت تحت إدارته أحد عشر شهرًا. وبعد وصوله إلى إسطنبول مثل بين يدي السلطان سليمان القانوني وأطلعه بشكل مفصل على جميع ما حصل له في غزواته السابقة، وقام بعدد من الزيارات الرسمية. اتجه بعد ذلك إلى مصنع بناء السفن ليرى التطورات التي حدثت أثناء غيابه، ثم أمر رئيس المهندسين ببناء ثلاثين سفينة من نوع قادرغة ليخرج بها للغزو برفقة السلطان سليمان في حملته الهمايونية السابعة.
في سنة 1537م أعلن السلطان سليمان القانوني الحرب على البندقية بعد استمرار معاهدة الصلح بين الدولتين مدة 35 سنة، ومن أسباب هذه الحملة قيام البندقية بتقديم المساعدة المستمرة خفية لألمانيا وإسبانيا، ورفضها دعوة الديوان للاتفاق العثماني الفرنسي. وفي 1 ذو الحجة 943هـ/11 مايو 1537م خرج خير الدين بالأسطول العثماني متوجهًا نحو كورفو وأوترانتو، ولحقه السلطان سليمان بالجيش بعد ستة أيام في 7 ذو الحجة/17 مايو. كان الأسطول مكونًا من 280 قطعة بحرية، عليها ثلاثون ألف جداف، وعشرات الألوف من جنود البحرية، وأربعة آلاف إنكشاري، وستمائة مدفع بري، وعدة آلاف من فرسان السباهية. وفي 11 يوليو دخل الجيش والأسطول العثماني خليج آفلونيا قبل السلطان بيومين، ثم اجتاز الأسطول مضيق أوترانتو وتم فتح أوترانتو في 23 يوليو 1537. يشير خير الدين في مذكراته إلى واقعة حدثت بعد دخوله إلى بحر الأدرياتيك، حيث لمح قطع كبيرة من أسطول البندقية فأمر بالهجوم عليها، فتم إغراق أربعة عشر سفينة من نوع قادرغة، وتم الاستيلاء على ستة عشر سفينة أخرى من ذات النوع، بينما لاذت بقية وحدات الأسطول بالفرار. ولم يلبث السلطان في البندقية حتى قفل راجعًا إلى إسطنبول برًا، وقام خير الدين بتسليم القسم الأكبر من الأسطول للطفي باشا ليبحر به الأخير إلى إسطنبول، وتوجه هو لغزو بعض الجزر.
لم يعني انتهاء حملة السلطان سليمان على البندقية وفك الحصار عن كورفو نهاية الصراع بين الدولة العثمانية وجمهورية البندقية، إذ أن هذا الصراع استمر لفترة في البحر، فبعد أن انتهت رحلة خير الدين إلى البندقية، غادرها على رأس ستين أو سبعين سفينة فقام في البداية بغزو جزيرة "كيفالونيا" التي كانت خاضعة لسيطرة البندقية آنذاك (تتبع اليوم لليونان)، ثم واصل طريقه نحو الجنوب الشرقي، وهاجم جزيرة "" التي كانت أيضًا تابعة للبندقية آنذاك، وغنم الجيش العثماني من هذه الجزيرة غنائم كثيرة، ثم حاصر بعض الجزر الأخرى عند خليج أجانيطس لمدة ثلاثة أيام، واستولى عليها في نهاية هذه المدة. ثم هاجم جزر "مرتد" و"باروس" و"أنتيباروس" اليونانية الواقعة في بحر إيجة واستولى عليها. ثم جاء "جزر كيكلاد" في سبتمبر 1537م الواقعة في جنوب بحر إيجة، وقد كانت هذه الجزر تحكم من قبل "" التابعة للبنادقة. تجول خير الدين في كافة الجزر الواحدة تلو الأخرى وأجبر الدوق "" على إعلان تبعيته للعثمانيين وتسديد مبلغ خمسة آلاف ليرة ذهبية كضريبة سنوية. واستطاع خير الدين فيما بعد السيطرة على عدد من الجزر مثل "سيروس" و"نيوس" و"تينوس" و"بطمس" و"" و"أستيباليا".
في945هـ/1538 أرسل السلطان سليمان القانوني خير الدين إلى الغزو مجددًا في بحر إيجة، إلا أن هذه الرحلة لم تتم بسهولة كما كان متوقعًا، فقد أدرك خير الدين ضرورة زيادة عدد سفن الأسطول العثماني، ولهذا السبب طالب العاملين الترسانة بإنشاء هذه السفن على الفور، وكان يأمل في الانتهاء من إنشاء 100 سفينة بعد الحصول على موافقة السلطان. وبينما كانت السفن في طور الإنشاء، طُلب الخروج إلى البحر، إلا أنه اعترض على هذه الفكرة نظرًا لأن السفن لم تجهز بعد. تشير بعض المصادر أن بعض وزراء الديوان لجئوا إلى حيلة لحثه على الخروج إلى البحر. فأشاعوا خبرًا مفاده أن أندريا دوريا وصل إلى جزيرة كريت، وينتظر بصحبة 40 سفينة لمهاجمة الأسطول العثماني الذي يقوده صالح ريس -المكون من 20 قطعة بحرية- وفي طريقه لحلب بضائع الهند من مصر. فهرع بربروس منطلقًا على رأس السفن التي كانت بحوزته بتاريخ 9 محرم 945هـ/7 يونيو 1538 وتشير بعض المصادر إلى الأخرى أن ذلك كان في 9 صفر/7 يوليو. وقد معه في هذه الرحلة 40 سفينة، كما كانت 90 سفينة تخضع لعملية البناء ستلحق بأسطوله فور الانتهاء من إنشائها. وقد استقبله السلطان إلى البحر، كما ودعه رجال وأركان الدولة حتى الميناء. عندما علم خير الدين أن أندريا دوريا لم يصل إلى جزيرة كريت، عمد إلى فتح بعض الجزر في بحر إيجة، ولما وصل إلى جزيرة "" أخرج 17 مدفعًا قابلًا للاستخدام من سفينة غارقة عند سواحلها. ثم بعد ذلك فتح الأسطول العثماني جزيرة "سكياثوس" بعد حصار دام لمدة ستة أيام، وتم أسر ثلاثة آلاف وثمانمائة شخص. وفي تلك الأثناء وصل من إسطنبول 90 سفينة اتحدت مع أسطول صالح ريس المؤلف من 20 سفينة، وانضما إلى أسطول خير الدين، ليرتفع بذلك عدد سفن الأسطول العثماني إلى 150 سفينة، وتمت إعادة اثنا عشر سفينة من هذا الأسطول إلى "جاليبولي" لنقص تجهيزاتها. وأُرسل الجزء الباقي من الأسطول صوب جزيرة "وابية". وحينها قام خير الدين بفتح جزيرة "سكيروس" وبعث الغنائم التي ظفر بها من الجزيرة إلى العاصمة إسطنبول. ثم بسط سيطرته من الشمال إلى الجنوب على التوالي على جزيرة "أندروس" و"تينوس" و"سريفوس" و"سكوربينتا".
توجه خير الدين بعد ذلك نحو جزيرة "كريت" بعدما فرغ من أنشطته في جزر "سبورات" و"كيكلاد". وقد كانت جزيرة كريت خاضعة لحكم جمهورية البندقية، وإن إخضاع البنادقة للجزيرة تحت سيطرتهم يمنحهم إمكانية التحكم الكامل في بحر إيجة، لذلك كان العثمانيون على وعي تام بأن استيلاءهم على هذه الجزيرة يعني إحكام السيطرة على بحر إيجة بأكمله. وأدرك خير الدين وقتها أهمية هذه الجزيرة، وتيقن أن قواته غير كافية لمهاجمتها والسيطرة عليها لكبر حجمها، فخطط لإرسال بعض جنوده في هجمات مفاجئة على الجزيرة لتدمير المواقع الهامة بها، وفي نفس الوقت تكون هذه الهجمات المباغتة بمثابة إعداد جيد لأي هجوم كبير محتمل تقوم به قواته في المستقبل. وصل أسطول خير الدين إلى جزيرة كريت على مشارف قلعة "كاندية"، فهمّ جنوده بتدمير نحو عشرين قرية قريبة من منطقة "ميلابوتاما" بالجزيرة، ومن ثم هاجموا مدينة "ريثيمو". بعدها وصلوا إلى منطقة يطلق عليها اسم "أبوكوران" في الجزيرة، واستولوا على ثمانية قرى واقعة فيها، وفتحوا الأماكن المحيطة بها، وانتقلوا إلى منطقة "خانيا" الواقعة غرب جزيرة كريت، ودافع أهلها باستماتة محتمين بقلعتها الحصينة، مما دفع خير الدين إلى التخلي عن حصار المدينة لمدة طويلة، وآثر الإغارة على المدن والقرى المجاورة لها. وبعد استمرار هجمات العثمانيين لمدة شهر متواصل، اتجه خير الدين نحو "كارباثوس" واستولى عليها، ثم أقام بها عشرة أيام. وفي تلك الأثناء بسط سيطرته على جزيرة "". مر الأسطول العثماني بعد ذلك على بعض الجزر المجاورة لجزيرة رودس، إلا أن رياح السموم قد هبت بشدة على سفنه، مما أنهك قوى مُجدفي سفن الأسطول، فأمرهم خير الدين بالاستراحة لمدة في جزيرة "كوس". وانضم للأسطول العثماني في هذه الجزيرة بعض المجدفين النصارى، كما لحق بهم بعض المجدفين القادمين من الأناضول، وبعد أن حصل الأسطول على بعض احتياجاته الضرورية في هذه الجزيرة، انطلق إلى جزيرة "أستروبالاي" واستولى عليها. قد كان مجموع الجزر والقلاع التي سيطر عليها خير الدين كما يشير في مذكراته ثمانية وعشرين جزيرة وسبع قلاع كانت تابعة لجمهورية البندقية، جعل على كل منها حامية لحمايتها، وقام بالإغارة على "أغريبوز" فبلغ عدد الأسرى الذين وقعوا بيده إلى عشرين ألف أسير، قام بإرسالهم جميعًا إلى إسطنبول. وقد كان ذلك تقريبًا في يوليو 1538م.
كانت النشاطات التي يزاولها خير الدين في البحر الأبيض المتوسط وبحر إيجة باسم الدولة العثمانية تثير حنق الإمبراطور الإسباني شارلكان أكثر من أي وقت مضى، ولم يكن الإمبراطور وحده في ذلك، بل كان بابا الفاتيكان "بولس الثالث" يسارع هو الآخر في عقد تحالفات ضد العثمانيين، حتى أنه سعى في الإصلاح بين الإمبراطور الإسباني كارلوس الخامس وملك فرنسا فرانسوا الأول، ومن جهة أخرى كان حكام البنادقة يعقدون تحالفات سرية ضد الدولة العثمانية، على الرغم من صداقتهم معهم منذ فترة طويلة، كما كانوا يعدون العدة لقتالهم، وفي نهاية المطاف عقدت جميع الأطراف العزم على تجميع أساطيلها عند ساحل جزيرة كورفو للرد على آخر غزوة خرج فيها خير الدين إلى جزر بحر إيجة. وقد تجمع عند جزيرة كورفو عدد كبير من السفن ذات التجهيزات المتفوقة من أساطيل عدد من الدول الأوروبية، وهي: جمهورية البندقية ودوقية مانتوفا والإمبراطورية الإسبانية والإمبراطورية البرتغالية والدولة البابوية وجمهورية جنوة وفرسان مالطا، وقد سُمي هذا التحالف بالعصبة المقدسة. تذكر المصادر أن أصحاب هذا التحالف قد اجتمعوا على فكرتين رئيسيتين، الأولى رغبة الإمبراطور شارلكان في الاستيلاء على الجزائر التي تمثل قاعدة للعثمانيين في أعمالهم البحرية، والفكرة الثانية كانت عزم حكام البندقية على استعادة الجزر التي فتحها العثمانيون حديثًا.
وصلت سفن البندقية أولًا إلى جزيرة كورفو -مكان تجمع الأسطول المسيحي-. وبعد ذلك بفترة قدمت سفن الأسطول البابوي بقيادة الأميرال "" الذي شعر بالملل جراء انتظار بقية السفن المسيحية، فقام بمهاجمة قلعة "بروزة" بأسطوله المكون من 83 قطعة بحرية، إلا أن قوات "حسين شاه بك" حاكم "" -التي كانت بروزة تابعة لها- صدّت هجوم غريماني، وبينما كان حسين شاه بك يحاول صد هجوم الأسطول البابوي كان يبعث الرسل إلى السلطان سليمان القانوني الذي كان يغزو "البغدان" لإبلاغه بهذه التطورات. وأخذ غريماني في قصف القلعة بالمدافع من البحر، كما أنزل جنوده إلى سواحل المدينة، لكن حسين شاه بك قام بهجوم مباغت من داخل القلعة واستطاع خطف هؤلاء الجنود. فلجأ غريماني إلى تشديد القصف على القلعة من البحر، وأنزل جنودًا آخرين إلى البر، إلا أنه لم ينجح في الاستيلاء على المدينة، إذ كبده الجيش العثماني خسائر كبيرة. واضطر في النهاية للعودة إلى جزيرة كورفو عندما سمع أن الأسطول العثماني في طريقه إلى بروزة.
ترامى إلى علم خير الدين خبر هجوم غريماني على بروزة بينما كان في جزيرة كوس فأرسل أسطولًا استكشافيًا بقيادة طرغود ريس على رأس عشرين سفينة لمعرفة المزيد من المعلومات حول قوات الأساطيل المسيحية، فصادف هذا الأسطول سفن الأسطول المسيحي المكون من 40 سفينة، فعاد مسرعًا وأخبر خير الدين بأن المسيحين تجمعوا عند سواحل بروزة، وفي نفس الوقت كان خير الدين يحصل على العديد من الأنباء والمعلومات ومستجدات الأوضاع في هذا الشأن حتى حصل على معلومات مفصلة بخصوص التحالف المسيحي وعلم أنهم في طريقهم لتنظيم هجمة مشتركة عليه. تحرك خير الدين على رأس أسطوله المكون من 122 سفينة إلى مدينة بروزة ومعه عشرون ألف جندي من رجال البحر والمدفعيين ما عدا المجدفين. وأما عدد سفن أسطول التحالف المسيحي فتتفاوت المصادر التاريخية في تحديد أعدادها، وأشار خير الدين في مذكراته أنه قد كان مكونًا من أكثر من ستمائة سفينة منها ثلاثمائة وثمانية سفن بحرية، ومائة وعشرون سفينة كبيرة لنقل الجنود. ويقوم بدفع الأسطول الآلاف من الجدافين، وأنه تم نقل ستين ألف جندي على متن هذا الأسطول. وعندما وصل خير الدين إلى بروزة استعدادًا لمنازلة الأسطول المسيحي، وصل القبطان الجنوي أندريا دوريا الذي كان مكلفًا بقيادة الأسطول في 2 جمادى الأولى 945هـ/25 سبتمبر 1538م.
قبل بدء المعركة جمع خير الدين قادة سفن أسطوله، وتشاور معهم حول الإجراءات التي سيتخذونها أثناء القتال. وقد أوصى بعض القادة خير الدين بإنزال عدد من الجنود والمدافع إلى ساحل المدينة للتمكن من مواجهة الكثرة العددية لقوات التحالف، فلم يعرب خير الدين في البداية عن إعجابه بهذه الفكرة، إلا أنه سمع بعد ذلك بمحاولات إنزال التحالف قواته إلى البر، فأسرع إلى إنزال جنوده إلى الساحل، واستطاع وقف إنزال جنود التحالف إلى الشاطئ عبر قصفه سفن الأسطوال بوابل من قذائف المدفعية. وبعد ذلك أخذت قوات التحالف بقصف ساحل المدينة بالمدفعية، لكن بعض قادة الأسطول بادروا إلى إجبار سفن التحالف على التراجع والانسحاب عن طريق الخروج بسفنهم أمام الأسطول. تحركت قوات التحالف نحو مضيق بروزة حتى وصلته وبدأت بمهاجمة السفن العثمانية الراسية في بروزة، فأمر خير الدين بقرع الطبول ورفع راية الحرب، والتحرك إلى الأمام. وتقدم الأسطول العثماني حتى مسافة 6 أميال، ومن ثم رسا، وانتظر حتى وصلت سائر السفن الأخرى لتنضم إليه، وعند انضمامها له شرع في مهاجمة سفن التحالف بقصفه بالمدفعية، ومع حلول الظلام بدأت سفن التحالف في الانسحاب من المنطقة، كما عاد خير الدين إلى الخليج وجمع قادته لمناقشة الأمور المقرر إنجازها في المستقبل.
تحرك دوريا بموجب القرارات التي اتخذها مجلس الحرب الخاص بالتحالف المسيحي نحو مدينة ليبانت للهجوم عليها وذلك لإجبار خير الدين على الخروج من بروزة لقتاله، وقد انطلق أسطول التحالف بقيادة دوريا في ساعات الصباح الأولى من يوم 4 جمادى الأولى 945هـ/25 سبتمبر 1538م، وفي صباح اليوم ذاته أبحر الأسطول العثماني نحو جزيرة كورفو. وأثناء إبحارهم كلف خير الدين بعض رجاله بالصعود إلى صواري السفن لمراقبة الأوضاع من بعد، فشاهد هؤلاء المراقبون بعض سفن التحالف الراسية على مقربة من جزيرة ليفكادا. وعليه، فطن خير الدين لوجود أسطول التحالف في هذه المنطقة، فحول وجهة أسطوله نحو الجنوب. وعندما أشرقت الشمس أدرك دوريا أن الأسطول العثماني يبحر خلفه.
كانت الرياح في ساعات الصباح الأولى تهب في صالح أسطول التحالف، حتى أرهق ذلك البحارة الأتراك، لكن مع سطوع الشمس انقطع هبوب الرياح، لتتوقف حركة سفن التحالف الشراعية الكبيرة لأسطول التحالف، وفي تلك الأثناء بدأ خير الدين في الهجوم، مما أدهش دوريا وأصابه بالحيرة، فقضى عدة ساعات يفكر بتردد بالغ في دخول المعركة. وبعد مدة طويلة من التفكير قرر دخول المعركة، والتقى الأسطولان على بعد 3-4 أميال غرب ساحل جزيرة "ليفكادا". اتخذ الأسطول العثماني وضع الهلال، إذ كان بربروس في الجناح الأوسط، وكان معه في سفينة القيادة ابنه حسن وابنه بالتبني حسن آغا، وكان على رأس الأساطيل المتمركزة في الجناح الأوسط "سنان ريس"، و"جعفر ريس"، و"شعبان ريس". أما الجناح الأيمن فقد كان تحت قيادة "صالح ريس"، وكان الجناح الأيسر تحت قيادة "سيدي علي ريس"، وأما "طرغود ريس" فقد كان على رأس الأسطول الاحتياطي في المؤخرة، وجعل خير الدين "مراد ريس" و"صادق ريس" و"قوزلجة محمد" تحت إمرته. وأما أسطول التحالف فقد نظم نفسه بحيث كانت السفن الشراعية الكبيرة في المقدمة، تليها القوادس ذات المجاديف موزعة على ثلاث مجموعات، ثم السفن ذات المجاديف الصغيرة، وجاءت السفن من النوع الذي كان يضم الأشرعة والمجاديف في آن واحد في المؤخرة. وكان دوريا يتمركز في صف القوادس في الصف الثاني.
كان خير الدين يعلم بالتفوق العددي لسفن أسطول التحالف، لذلك لم يستسغ فكرة الهجوم عليها والالتحام معها وجهًا لوجه، فبدأ بمهاجمتهم بقصف مدفعي عن بُعد. وقد أحدثت المدفعية العثمانية بعيدة المدى خسائر كبيرة في صفوف التحالف، حيث قام خير الدين بجعل أسطوله في موقع يمكِّن القذائف من دك سفن التحالف، وفي المقابل لم تستطع قذائف أسطول التحالف -الأقصر من حيث المدى- الوصول إلى سفن الأسطول العثماني. فبادر دوريا بإصدار أوامره لأساطيله بالاقتراب من الأسطول العثماني، وأراد أن يطوق الأسطول العثماني من الخلف مستقلًا القوادس التي كانت في الصف الثاني من أسطوله، إلا أنه فشل في تنفيذ هذه الخطة بسبب اقترابه من مدى قذائف المدافع العثمانية التي لم تسمح له بذلك. وعمد دوريا إلى محاولة تنفيذ هذه الخطة مرة ثانية، إلا أن خير الدين أدرك هذا المخطط، واتخذ التدابير اللازمة لمواجهته. وبينما كان دوريا يرغب في تطويق سفن الأسطول العثماني عمد خير الدين إلى تغيير اتجاه سفنه، وضرب قوات التحالف من الجنب. وعندما حاول خير الدين إجراء مناورة عكسية، تحرك الأسطول العثماني في المقابل، ولم يعط فرصة لأسطول التحالف لمهاجمته. كان دوريا قد تمركز في صف القوادس الثاني لتيخذ السفن الكبيرة التي كانت في المقدمة كخندق يحتمي به لدى مهاجمة الأسطول العثماني، لذلك قام خير الدين بهجوم مباغت غير متوقع، فهجم فجأة على قوادس أسطول التحالف التي كانت في مقدمة دوريا وأحدث شقًا في صفوفها، وبدأ في الاشتباك معها. كما بادرت القوات العثمانية الاحتياطية إلى محاولة تطويق أسطول التحالف من جديد. ولقد أذهل هذا الهجوم الأخير الذي قام به خير الدين قادة أسطول التحالف بشكل كبير، ولهذا السبب بدأت سفنهم في التصادم ببعضها البعض، مما أحدث خسائر فادحة بين صفوفها. فأصدر دوريا أمرًا لأسطوله بالانسحاب بعدما أدرك أن الأمور بدأت في التدهور بعد المناورات الأخيرة. وفي تلك الأثناء هبت رياح شديدة أسفرت عن إصابة أسطول التحالف بحالة من التخبط، إلا أنها كانت سببًا في نجاتهم من بين يد الأسطول العثماني، لأن سفن أسطول التحالف استدارت حتى جعلت الرياح تهب من خلفها، وانطلقت مسرعة حتى هربت من ميدان المعركة. كان الليل قد بدأ يرخي سدوله فانتهز دوريا الفرصة وأمر جميع سفنه بأن تطفئ مصابيحها، واستطاع أن ينجو بنفسه مع نصف الأسطول في ظلمة الليل، إلا أن هذه الخطوة تسببت في نفس الوقت بإصابة معظم سفنه الهاربة بقذائف الأسطول العثماني، فلم ينج منها سوى القليل، وتوجهت تلك السفن الناجية صوب جزيرة كورفو.
استمرت المعركة خمس ساعات، فقد أسطول التحالف فيها 60 سفينة، وسقط من قواته 2775 جنديًا أسيرًا في أيدي العثمانيين. ولم يفقد فيها الأسطول العثماني سوى بضعه سفن، وفقد 800 جندي بين قتيل وأسير. وقد منعت ظلمة الليل والرياح الشديدة أي محاولة لتعقب سفن أسطول دوريا. أرسل خير الدين في الحال ابنه بالتبني حسن آغا إلى السلطان سليمان القانوني لإخباره بنبأ النصر. وتلقى السلطان هذا النبأ وهو عائد من غزو البغدان، واستمع إلى رسالة نصر التي بعثها خير الدين، فأمر بإعلان النصر في جميع الولايات العثمانية، كما أصدر أوامر بمنح خير الدين مائة ألف قطعة نقود فضية كمكافأة له هذا الإنجاز. وبعد أن مكث خير الدين عند سواحل بروزة لمدة تتراوح بين خمسة عشر إلى عشرين يومًا، استولى على جزيرة كيفالونيا، ثم انطلق من سواحل اليونان الغربية إلى إسطنبول لقضاء فصل الشتاء بها.
كانت الحرب العثمانية البندقية ما زالت مستمرة بين الطرفين، فبعد هزيمة الصليبيين في معركة بروزة قام البنادقة بشن هجمات متتالية على الحدود الغربية للدولة العثمانية مما دفع أمير "غازي خسرو بك" إلى الاستيلاء على قلعة "نين" الخاضعة لحكم البنادقة الواقعة غرب مدينة "زادار"، حتى إنه تمكن من إحباط هجوم شنه البنادقة على قلعة "نادين". لكن مدينة "كاستيلنوفا" (تسمى اليوم ب وتقع في دولة الجبل الأسود) الواقعة على الساحل الشمالي لخليج "كاتارو" والتابعة لسنجق البوسنة، تعرضت بعدها بفترة لهجوم من أندريا دوريا الذي أراد الثأر لهزيمته في معركة بروزة. فما إن سمع دوريا بمغادرة خير الدين للسواحل اليونانية، حتى وصل إلى مدينة "كاسيلنوفا" وحاصرها -وقد كان ذلك بعد شهر واحد من هزيمته في بروزة-. وأنزل جنوده إلى ساحل المدينة، وأمطرها بوابل من القذائف المدفعية، فاستمات المدافعون من الجنود العثمانيين عن المدينة في حمايتها، وأقدموا على بعض المحاولات للخروج من قلعة المدينة، إلا أن الغالبية العظمى من قواتهم قد سقطت في هذه المحاولات، وقلّ عددهم، مما دفعهم في إلى الاستسلام في نهاية الأمر. وقام دوريا بعدها بتسكين حامية تتكون من ستة آلاف جندي في هذه المدينة، ولم يستطع "خسرو بك" من استرداد المدينة رغم كل المساعي التي بذلها في هذا الصدد. فأوكل السلطان سليمان القانوني أمر استرداد المدينة إلى خير الدين، فقدمها الأخير على رأس أسطول مكون من مائة وخمسين سفينة، وكان "خسرو بك" قد وصل هو الآخر بقواته. فقامت القوات العثمانية بمحاصرة قلعة المدينة على مدار عشرين يومًا، واستطاعوا في النهاية استرداد المدينة بعد قصفها بالمدافع، وفتح ثقوب في جدرانها، فانسل عدد من الجنود العثمانيين إلى داخلها، وسهلوا السيطرة عليها. وقد كان ذلك في 25 ربيع الأول 945هـ/24 أغسطس 1539م.