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.
Meskipun kalah dalam pertempuran, Aruj berhasil meloloskan diri namun pasukannya tertangkap oleh musuh. Karena rasa solidaritas yang tedapat dalam dirinya, dia memutuskan untuk kembali dan berniat membebaskan para pasukannya. Aruj kembali melakukan pertempuran, namun sayangnya pada kali ini dia gugur dalam pertempuran.
Menurut Profesor Idris Boston dari Istanbul University, Khairuddin kemudian diangkat menjadi admiral yang selanjutnya menjadi inisiator berdirinya angkatan laut Turki.
Ketika Sultan Selim I digantikan oleh putranya Sultan Sulaiman, Khairuddin diangkat menjadi Komandan Angkatan Lautnya. Karena kehebatannya ia dijuluki "Singa Laut Mediterania" yang dihormati kawan dan ditakuti lawan.
Melihat laut Mediterania dikuasai Kesultanan Turki Utsmani, membuat Paus Paul III pada tahun 1538 mengorganisir pasukkan laut sebagai bagian dari Tentara Salib, dipimpin oleh seorang pelaut asal Genoa bernama Andrea Doria yang didukung 250 kapal perang.
Mereka kemudian berhadapan dengan pasukan Khairuddin yang hanya didukung oleh 122 kapal, yang tentunya sangat tidak seimbang. Pertempuran ini terjadi pada 28 September 1538, di Preveza. Dalam pertempuran ini, 10 kapal pasukan Salib ditenggelamkan, 30 kapal ditahan tanpa kehilangan satu kapalpun, dan sekitar 1000 pasukan Salib ditahan. Pertarungan antara Khairuddin Barbarossa dengan Andrea Doria ini dikenal dengan nama Battle of Preveza.
Atas prestasinya ini, Khairuddin kemudian diundang ke Istana Topkapi oleh Sultan Sulaiman untuk menerima anugrah Kaptan-i-Derya (Chip of Admiral) angkatan laut Turki, sekaligus sebagai beylerbey  (Governor of givernors) Turki Utsmani di Afrika Utara.
Khairuddin Barbarossa ini sangat dikenang sebagai pahlawan bangsa Turki, bahkan kehebatannya tersebut disejajarkan dengan para sultan Turki Utsmani yang hebat seperti Muhammad Alfatih dan Sulaiman Alkanuni.
Khairuddin Barbarossa menghembuskan nafas terakhirnya di usia 68 tahun dengan sangat tenang di kamar pribadinya. Namun versi lain menyebutkan bahwa Khairuddin Barbarossa meninggal pada usia 78 tahun, pada tahun 1546. Pada saat itu Khairuddin Barbarossa memimpin pasukan untuk merebut Malta dari tangan Knight of St. John dari Britania Raya. Namun dalam pertempuran itu, Khairuddin gugur. Khairuddin dimakamkan di Istanbul, Turki.
Namun sayangnya, banyak sejarah yang ada menceritakan kisah Khairuddin Barbarossa yang berkebalikan dengan apa yang kita baca atau lihat di film sekarang ini. Entah apa alasannya, namun ada indikasi kalau bangsa Barat seperti ingin mengubah cerita sejarah dengan memelintir kisah sang pelaut jenius ini. Bangsa-bangsa barat kemudian hari memelintir cerita aslinya sehingga menunjukkan sifat Barbarossa yang berkebalikan dengan aslinya.
