الشرق فقد كان بربروسه أقل توفيقا منه في الغرب، فقد تقدم جيش تونس نحو الجزائر، فخرج خير الدين لملاقاته، والتقى به في أرض القبائل في فلست يملليل، وتخلى عنه سلطان كوكو في إبان المعركة وحارب الترك، وكان السلطان الحفصى قد استماله سرا، ونزلت بالترك هزيمة منكرة، واضطر بربروسه إلى الالتجاء إلى جيجل بعد أن سد الطريق أمامه إلى الجزائر. وفي خلال هذه المدة خرب أهل القبائل متيجة واحتلوا الجزائر في حين ثارت شرشال وتنس مرة أخرى عام ١٥٢٠.
وأخذ خير الدين وهو في ملجئه جيجل يعيد تنظيم جيشه ويجمع الأمداد. واستأنف مهنته القديمة وهي القرصنة، وسلب الشواطئ الغربية للبحر المتوسط فيما بين عامى ١٥٢٠ و ١٥٢٥ وجمع أسلابا هائلة، كما التف حوله عدد كبير من المغامرين، وسرعان ما غدا من القوة بحيث استطاع الاستيلاء على كللو collo عام ١٥٢١، وعلى بونة عام ١٥٢٢ وقسطنطينة، كما ضم إلى جانبه أهل القبائل الصغرى بتحالفه مع عبد العزيز زعيم بنى عباس ومنافس سلطان كوكو. فاستطاع في عام ١٥٢٥ العودة إلى منازلة ابن القاضى، وأوقع به الهزيمة عند وادي بقدورة ثم عند ممر بنى عائشة، وقتل ابن القاضى بيد جنوده. وعاد الترك فاحتلوا متيجة والجزائر، وقتلوا زعماء الثوار في تنس وشرشال، وعاقبوا أهل قسطنطينة عقابا شديدا لأنهم طردوا قائدهم عام ١٥٢٧ وقتلوا الحامية التركية. وأخيرا قدم حسين خليفة ابن القاضى ولاءه لهم واتفق على دفع جزية سنوية للترك (١٥٢٨).
واستولى خير الدين على بنون Penon. وهو معقل أسبانى بنى على جزيرة صغيرة على مرمى قذيفة مدفع من الجزائر، وبذلك استعاد الترك سلطانهم على تلك الجهات. ففي بداية شهر مايو من عام ١٥٢٩ بدأ بربروسه في ضرب هذا المعقل بالمدافع، وكانت حاميته الإسبانية قد أهملت تحصينه، فسقط الحصن عنوة في ٢٧ مايو بعد أن جرح جل رجاله، ولم يسلم منهم سوى ٢٥ رجلا. وأمر خير الدين بقتل حاكم هذا الحصن دون مارتن ده فار كاس Don Martin de Vargas كما أمر