اجتذب الصراع بين الإسلام والنصرانية (الأسبانية خصوصًا) في الحوض الغربي للبحر المتوسط في أوائل القرن العاشر الهجري (السادس عشر الميلادي) عددًا كبيرًا من البحارة المغامرين، الذي نشأوا في خدمة الأسطول العثماني، ثم راحوا يكوّنون أساطيل صغيرة تعمل لحسابهم الخاص وتجاهد ضد أعداء الدين. ومن هؤلاء الأخوان عروج وخير الدين الذي عُرِف ببربروسة، أي (ذي اللحية الحمراء) . فقد بدأ الأول نشاطه في غربي البحر المتوسط حوالي سنة 916هـ، 1510م، وفتح له الأمير الحفصي موانئ إفريقية. ولما سمع أهل المغرب الأوسط بغاراته الناجحة على الأسبان استقدموه إلى بلادهم، ليساعدهم على استرداد بجاية أكبر موانئ شرق الجزائر آنذاك. ثم استدعاه حاكم ميناء الجزائر، فنجح مع قوة عثمانية صغيرة في صد هجوم أسباني عن المدينة سنة 922هـ، 1517م. وحين خان بعض أهل تلمسان عروجًا اضطر للفرار فتتبعته القوات الأسبانية وقتلته وهو في طريقه إلى الجزائر.
تحرّج موقف خير الدين بالجزائر، فاستعان بالسلطان العثماني سليم سنة 924هـ، 1518م. فأرسل له السلطان ألفي إنكشاري وسمح لرعاياه بالتطوع في جيش المغرب، ودخلت الجزائر ضمن الولايات العثمانية. لكن كان على خير الدين أن يجاهد في جبهتين إحداهما ضد دول أوروبا وأسبانيا بخاصة، والأخرى توحيد البلاد في قوة إسلامية تواجه خصومه في المتوسط، فنجح في صراعه مع أوروبا وإلى قدر كبير في طرد الأسبان من الموانئ التي كانوا يحتلونها على سواحل المغرب الأوسط، باستثناء وهران التي ظلت تحت السيطرة الأسبانية حتى القرن الثامن عشر. وقد واجه في سبيل ذلك مؤامرات الحفصيين بإفريقية وبني زيان وغيرهم من القوى المحلية. لكن نجاحه سنة 936هـ، 1529م في القضاء على حصن البينون الأسباني، كان بداية حقيقية لتأسيس ولاية الجزائر وتحول ميناء الجزائر إلى عاصمة للمغرب الأوسط.