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

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