Nama Barbarossa ini sebenarnya berasal dari dua nama yaitu Khairuddin Barbarossa dan Aruj Barbarossa. Mereka merupakan kakak-beradik yang sering berlayar di perairan antara Turki dan Yunani. Nama Barbarossa sendiri berasal dari bahasa Spanyol yang artinya janggut merah.
Pada suatu ketika Aruj bersama adik-adiknya sedang berlayar, kapal mereka tiba-tiba diserang oleh kapal St. George of Jerusalem atau lebih dikenal dengan Knight of Rhodes. Yang menyebabkan adik bungsu mereka terbunuh. Setelah penyerangan yang menewaskan adik Aruj tersebut, dia dan adiknya yang lain yaitu Khairuddin memutuskan untuk menjadi bajak laut dan berniat balas dendam dengan menyerang kapal-kapal militer Eropa. Hingga akhirnya mereka terkenal dengan nama Barbarossa Brothers.
Pada saat itu, Islam sempat memegang peradaban tingkat tinggi di Andalusia, Spanyol. Kota-kota di Andalusia bisa dikatakan sangat maju seperti di Cordoba, Granada, dan Sevilla. Di bawah kepemimpinan Bani Umayyah pada tahun 756 M. Sampai akhirnya meletuslah peristiwa Perang Salib gelombang pertama, yang bertujuan merebut kota suci Yerusalem atau Al Quds dari tangan ummat Islam. Saat itu Spanyol dipimpin oleh Raja Ferdinand II, setelah menikah dengan Ratu Isabella dari Castille, mereka melakukan pembersihan etnis terhadap orang-orang Arab yang beragama Islam dan penganut Yahudi.
Ferdinand dan Isabella menyediakan tiga pilihan: Berganti agama menjadi Katolik, meninggalkan Spanyol, atau menghadapi pedang tentaranya. Peristiwa ini kemudian dikenal dengan "Reconquista". Satu persatu kota-kota yang diperintah oleh kesultanan-kesultanan Islam di Andalusia dengan mudah ditaklukkan dan diambil-alih.
Ummat Islam dan Yahudi yang kehilangan perlindungan, harus menyelamatkan nyawa mereka dengan cara menghindari tentara Spanyol, kemudian secara tergesa-gesa meninggalkan Andalusia dan menuju pantai Afrika Utara.
Setelah Reconquista tuntas di daratan Spanyol, upaya pembantaian diteruskan dengan menyusuri pantai Mediterania di Afrika Utara dan terus ke arah Timur menuju kota suci Jerusalem.
Aruj dan Khairuddin, mereka sering menyerang kapal-kapal Kristen yang membuat nama mereka semakin terkenal, yang kemudian menimbulkan rasa takut para nakhoda kapal-kapal asal Eropa yang melintas laut Mediterania.
Kisah Khairuddin yang lahir di pulau Lesvos, Yunani pada tahun 1478, dengan nama kecil Khidr ini, sampai ke telinga Sulthan Sulaiman I. Pemimpin Turki Utsmani pada waktu itu.
Kesultanan Turki Usmani di Istanbul kemudian memberikan dukungan, sekaligus mengubah misi balas dendam Aruj dan Khairuddin menjadi misi penyelamatan para pengungsi dari Andalusia yang terus dikejar oleh tentara Katolik Spanyol. Kemudian Barbarossa Brothers direkrut oleh Sultan Sulaiman I yang membuat nama mereka semakin besar.
Mereka menjadikan Aljazair sebagai pangkalan mereka. Karena Barbarossa Brothers ini direkrut oleh Sultan, mereka akhirnya menjadi privateer.
Pada tahun 1518, Spanyol berhasil menghasut pemimpin kota Tlemcen, Aljazair. Untuk memberontak terhadap Barbarossa Brothers, akhirnya Aruj memberikan kepemimpinan Aljazair kepada Khairuddin. Kemudian Aruj beserta pasukannya berangkat menuju Tlemcen, namun karena musuh yang dilawan oleh Aruj merupakan sesama muslim, menjadikan Aruj tidak fokus terhadap pertempurannya dan menyebabkan dia kalah dalam pertempuran tersebut.
