بعدَ عودتِهِ منْ جيجلَ إلى الجزائرِ عمِلَ خيرُ الدينِ فوراً على إعادَتِهَا إلى وضعِها السابقِ حينما كانتْ تحتَ حكمِهِ، فبدأَ أولاً بالضربِ على أيدي المتمردينَ بشدَّةٍ، ودأبَ خلالَ سنَتَيْ 932هـ-933هـ /(26-1527)م على ملاحقةِ العصاةِ، فألْقَى القبضَ على حاكِمَِيْ تنسَ وشرشالَ وقتلَهُما، وفرضَ سيطرتَهُ مجدَّدَاً على الساحلِ من جيجلَ حتى وهرانَ. وفي سنةِ 1528م (934هـ-935هـ) تمرَّدَتْ قُسَنْطينَةَ وقُتِلَ عاملَ خيرِ الدينِ عليها حتى كادتْ تسقطُ بيدِ المتمردينِ، فاضْطُرَّ خيرُ الدينِ ذلكَ العامِ لتوجيهِ ضربةٍ قاسيةٍ للمدينةِ والقبائلِ المجاورةِ لها، وغدتِ المنطقةُ وما جاوَرَها خاليةً من السُّكَّانِ لشهورٍ وأضحتْ مأوىً للوحوشِ والأشقياءِ. وبعدَ مقتلِ أحمدَ ابنِ القاضي سلطانِ إمارةِ كوكو لمْ يعُدْ يواجِهُ أيَّ خطرٍ أو اعتراضٍ منْ أيِّ جهَةٍ، ولمْ يعدْ يخشى منْ جيرانِهِ أحداً إلاَّ أنَّ وجودَ الإسبانِ في حصن الصخرة (بنيون) بقيَ يُشَكِّلُ تهديداً ماثِلاً. شَيَّدَ الإسبانُ سنةَ 916هـ (1510)م قلعةً حصينةً على أرضٍ صخريَّةٍ تُدْعَى "البنيون" أي "حصنَ الصخرةِ" في عَرْضِ البحرِ على بعدِ ثلاثمئةِ مترٍ من مرسى الجزائرِ، وشَكَّلَ تمركُزُهُم فيها خطراً كبيراً ومباشراً على مدينةِ الجزائر، كما كانَ وجودُهُم -عدا عمَّا كانتِ السفنُ تواجِهُهُ من صِعَابٍ في غُدُوِّها ورَواحِها- يُعتَبَرُ بحقِّ الأهلينَ إهانةً كبيرةً، فضلاً عنْ أنَّهُم قبلَ قدوم الأخويْنِ بربروسَ كانُوا يُمْطِرُونَ مرسى الجزائرِ بقذائِفِهِمْ، فيُضطرُّ الأهلونَ للخضوع لهُمُ وقبولِ إملاءاتِهِمْ. ومعَ استقرارِ خيرِ الدينِ في الجزائرِ نهائيَّاً غدا طردُ الإسبانِ من القلعةِ ضرورةً محتَّمَةً لتعزيزِ سلطانِهِ من جهةٍ وضماناً للأمنِ لسفنِهِ وللميناءِ من جهةٍ أخرى، [وجاءتْ اللحظةُ المناسبةُ بإعلانِ السلطانِ سليمانَ القانونيِّ الحربَ على الإمبراطوريةِ الرومانيةِ المقدَّسَةِ مُبْتَغِياً غزوَ ڤيينّا، وأرادَ إشْغَالَ الإسبانِ وشارلكانَ عن إمدادِ النِّمْساٍٍ وصرفِ أنظارهِمْ عنها]. أرسلَ خيرُ الدينِ في مايو/أيار 1529 (935هـ) خطاباً لقائدِ القلعةِ "دون مارتن دي فرڠاس" يعلمُهُ بضرورةِ تسليمِهَا ومغادرتِهَا معَ جندِهِ دونَمَا أذىً يُصيبُهُمْ، لكنَّ القائدَ ردَّ بالرفض. شرعَ خيرُ الدينِ بقصفِ القلعةِ لعشرينَ يوماً وتمكَّنَ منْ اقتحامِهَا في 17 رمضان 935هـ/26 مايو /أيَّارَ 1529م، وبعد معركةٍ كبيرةٍ أعلنَ القائدُ استسلامَهُ معَ سبعمئةٍ منْ رجالِه. يذكرُ خيرُ الدينِ في مذكِّراتِهِ أنَّ الإسبانَ كانُوا يقومُون بقصفِ المَآذِنَ عندما يسمعُونَ الأذانَ من بابِ التسليةِ لكنَّهُمْ أقلعُوا عنْ فعلتِهِمْ الشنيعةِ تلكَ بعدَ استقرارِ الأخوَيْنِ بربروسَ في الجزائرِ. عَقِبَ استيلاءِ خيرِ الدينِ على القلعةِ جِيءَ إليه بقائدِ المدفعيةِ الذي كانَ دمَّرَ العديدَ منَ المَآذِنَ وقتلَ كثيراً من المؤذِّنينَ، فأمرَ بوضعِهِ في فُوَّهَةِ مدفعٍ وقَذَفَهُ إلى البحرِ، وضربَ عُنُقَ مساعدِهِ معَ عشرةٍ منْ جنودِ المدفعيةِ، أمَّا الباقُونَ فأُلْقُوا في الزنازين. أمرَ خيرُ الدينِ بتلغيمِ الصخرةِ وتفجيرِها، وحشدَ ثلاثينَ ألفَ أسيرٍٍ كانُوا يقْبَعُونَ في السجونِ فاستخدمُهُمْ لجمعِ صخورِ القلعةِ وبناءِ كاسرِ أمواجٍ يربُطُ الجزيرةَ بالميناءِ. بعدَ عشرةِ أيامٍ منْ سُقوطِها قدِمَتْ -بناءً لطلبِ قائدِ القلعةِ- تعزيزاتٌ منْ تسعِ سفنٍ إسبانيةٍ محمَّلَةٍ بالمؤنِ والأسلحةِ والمعدّاتِ فلمْ تجدْ لهَا أثَرَاً، ولمَّا اقتربتْ أكثرَ ولمْ ترَها ظنَّت أنَّها ضَلَّتِ الطريقَ، وفيما هيَ تُحاوِلُ تلمُّسَ طريقِها إذْ بخمسَ عشرةَ سفينةً منْ سفنِ خيرِ الدينِ تحاصِرُهَا منْ كلِّ جهة. تمَّ القضاءُ على معظمِ جندِ السفنِ فيما استسلمَ ثلاثمئةٍ وخمسةٍ وثلاثونَ. تركتِ الحادثةُ انطباعاً عميقاً لدى الإسبانِ بأنَّه لمْ يعُدْ بمُكْنَتِهِمُ الاقترابُ منْ سواحلِ الجزائرِ.