1516年海雷丁等人從西班牙手中奪取吉傑利和阿爾及爾。當地西班牙人向國王兼神聖羅馬帝國皇帝查理五世求援，不過西班牙艦隊面對海雷丁兄弟也無可奈何。自此，他們成了阿爾及爾一帶真正的統治者，老二自立爲蘇丹。世界史上絕無僅有的海盜王國巴巴羅薩王朝正式誕生了。
史上有兩個“巴巴羅薩”。它們之間幾乎毫無關聯。
第一個是霍亨斯陶芬王朝的腓特烈一世(1123-1190年)，他是德意志國王(1152-1190年在位)、神聖羅馬帝國皇帝(1155-1190年在位)。
他生活在一個動盪的時代。德意志內部，爲爭奪國王位置連年廝殺不休;而國王與教皇之間爲爭奪主教的各種權力，也爭鬥了數百年，最後還是難見分曉。那是一個尚武的時代，而他正是那個時代典型的尚武帝王，一生醉心於金戈鐵馬的生活。他窮兵黷武，嗜殺成性，三次強攻意大利，併發起十字軍東征，土耳其帝國在他腳下顫抖，基督教國家慘受蹂躪，屍橫遍野，血流成河，確實殘忍。
他綽號爲“紅鬍子”，因爲他有一臉鮮紅色的鬍子。但在意大利人看來，此綽號的含義是這個入侵者在意大利殘殺無辜，是意大利人的鮮血染紅了他的鬍子。在意大利語中，“紅鬍子”的譯音爲“巴巴羅薩”。因此，他也常被稱爲“巴巴羅薩”。他是希特勒最崇拜的人物，所以希特勒將他入侵蘇聯的計劃定名爲“巴巴羅薩”計劃。
第二個是奧斯曼帝國時期的大海盜海雷丁及其兄弟。
海雷丁並非其原名，而是蘇萊曼大帝賜予的，意爲“信任的美德”。海雷丁的父親雅庫布是一名土耳其穆斯林;母親是一名希臘基督徒，一說爲牧師的寡婦。大概在15世紀70年代，他的父親與其母親生下4男2女，海雷丁是兄弟中的老三，生於1466年前後。
雅庫布在希臘的米蒂利尼島上做陶工，還買了一艘船用於貿易。兄弟們都幫過老爹的忙，其中老二主要負責開船，而海雷丁則幫着做陶器。兄弟四人皆對海洋貿易有興趣，不過剛開始老大繼承了其父衣鉢，沒有出海;老二、老四結成一夥;海雷丁則自起爐竈。兄弟三人開始都只是普通水手，後來轉做海盜，從事私掠活動，與羅得島上的聖約翰騎士團分庭抗禮。海雷丁的兄弟主要活動於敘利亞、安納托利亞、埃及等地;他則在愛琴海發展，並於附近建立起自己的勢力。
不幸的是，在一次從的黎波里至黎巴嫩的返回途中，老二的船隊遭到聖約翰騎士團攻擊，結果老四戰死，老二本人則受傷被俘，關押在監獄裏差不多3年時間。後來海雷丁得知消息，前去救出哥哥。老二逃脫後試圖東山再起，他先後獲得土耳其王子和馬穆魯克蘇丹的賞識，並得到船隻支持。1503 年，海雷丁與他合夥行事。次年，他們獲得北非蘇丹准許，建造基地進行海盜活動，所得1/3歸蘇丹所有。
於是，不少來自教皇的船隻大遭其殃，甚至一艘西西里的軍艦也被他們俘虜，上面滿載着來自阿拉貢的380名西班牙士兵和60名騎士。1505年，他們襲擊了意大利的卡拉布里亞海岸。這些成就讓他們名聲大噪，許多有名的伊斯蘭海盜紛紛加入麾下。1508年，他們又突襲了意大利的另一處海岸。
也許是看着兄弟的海盜生意太紅火了，老大也於1509 年趕來投奔。1504至1510年間，老二的艦隊把許多穆斯林從西班牙撤回北非，這一舉動讓他獲得了很高的名望，人們送給他一個尊稱Baba，意思與中文的“爸爸”一樣。不過，這個名稱在歐洲大陸變成了Barbarossa(巴巴羅薩)，也就是著名的神聖羅馬帝國皇帝腓特烈的名字。
1510至1516年間，海雷丁三兄弟在西地中海橫行無忌，多次與正在染指北非的西班牙軍隊發生衝突。1512年8月，Bougie的流亡統治者請三兄弟趕走其領土上的西班牙人。在這次戰鬥中老二失去了左手，後來裝了一個銀假肢，他由此獲得“銀手臂”的綽號。
1516 年，西班牙國王去世，海雷丁等人趁機捲土重來，從西班牙手中奪取吉傑利和阿爾及爾，並趕走了這裏原來的統治者。當地的西班牙人向國王兼神聖羅馬帝國皇帝查理五世求援，不過西班牙艦隊面對海雷丁兄弟也無可奈何。自此，他們成了阿爾及爾一帶真正的統治者，老二自立爲蘇丹。於是，世界史上絕無僅有的海盜王國???巴巴羅薩王朝正式誕生了。
老二明白，單憑他們兄弟幾個是無法長期與西班牙對抗的，他們需要一個強大的靠山。於是，他選擇了奧斯曼土耳其。 1517年，老二廢除了自己的蘇丹稱號，並將阿爾及爾奉送給奧斯曼土耳其蘇丹謝利姆一世。謝利姆接受了這份禮物，將阿爾及爾設爲行省，任命老二爲當地長官，並統領西地中海的海事，同時爲他提供軍事物資。
西班牙人自然不能容忍一個海盜頭子沐猴而冠，即命令Tlemcen地方的軍隊由陸路進攻海雷丁三兄弟，但遭到失敗，而且 Tlemcen也落入海氏三兄弟手中。盛怒的西班牙人於1518年5月發動1萬軍隊，並聯合馬耳他騎士團、當地的貝多因人再次對他們進行圍剿。8月17 日，老二與老大率領1500名土耳其人及5000名摩爾人在Tlemcen抵抗了20天，最終不敵被殺。從此，海雷丁繼承了哥哥的財富及事業，包括“巴巴羅薩”這個名字。
藉助土耳其的強大實力，贈給他精兵2000名，他本人又招兵4000名，“復活”的“巴巴羅薩”??海雷丁於同年12月奪回了 Tlemcen。他繼續實行從西班牙運回摩里斯科人的政策，這使他獲得了廣大穆斯林的支持。1519年，他擊敗試圖奪回阿爾及爾的西班牙及意大利聯軍。此後，他橫行西地中海，不斷對法國南部、意大利沿岸、西班牙沿岸進行侵擾，許多港口的堡壘遭到破壞。他殘酷無情地到處實施洗劫，掠奪財富、人口，實行焦土政策，也給自己留下了“魔鬼海盜”的罵名。
1529年5月，海雷丁用買來的幾百門重炮連轟了6晝夜，攻下阿爾及爾港外佩農孤島上的西班牙城堡(要知道，西班牙人堅守了這個要塞29年)。整個阿爾及爾港不攻自破，被海雷丁徹底控制。同年8月，他攻擊西班牙的地中海沿岸，並連續7次幫助7萬名摩里斯科人從安達盧西亞逃脫。
1531年，查理五世命令安德魯在返回阿爾及爾的途中，還在墨西拿擊沉了馬耳他騎士團的一艘船。同年10月，他再次襲擊了西班牙沿岸。
翌年，奧斯曼蘇丹蘇萊曼大帝遠征奧地利，安德魯趁機攻佔了伯羅奔尼撒沿岸的一些地區。這讓蘇萊曼意識到一位優秀海軍指揮官的重要性。於是，他召喚海雷丁到伊斯坦布爾受命。海雷丁於當年8月組軍出海，一路推進，並在墨西拿附近俘獲18艘西班牙戰艦。根據俘虜的交待，海雷丁得知安德魯正前往希臘的普雷韋扎，便立刻迎頭趕上，與之打了一場仗，安德魯在損失了7艘戰艦後撤退。
這時的海雷丁麾下已經擁有44艘戰艦。不過他很狡猾，命令其中25艘返回阿爾及爾，自己帶着剩下的19艘回伊斯坦布爾覆命。蘇萊曼大帝對海雷丁的“豐功偉績”非常滿意，任命他爲奧斯曼土耳其的海軍元帥、北非首席長官，羅得島、埃維厄島、希俄斯島也歸他管理。
1534年，海雷丁從伊斯坦布爾率領一支由80艘戰艦組成的艦隊出征。同年4月，奪回西班牙人佔領的勒班陀等地，然後多次對拉齊奧、那不勒斯等意大利城市進行襲擊，羅馬的教堂經常響起警報。8月，他揮師南下，佔領突尼斯並趕走其蘇丹，將西班牙人全部逐出北非。
次年，海雷丁佔領了意大利美麗的卡普里島，那裏距意大利最富裕的城市那不勒斯只有很短的航程。在此前後，他還在意大利小島上建立了不少城堡，直到今天仍依然屹立在那裏。
突尼斯蘇丹向查理五世求救。於是，西班牙與意大利派出一支大軍??300艘戰艦、24 000名士兵前往北非。海雷丁自知難以匹敵，便主動放棄突尼斯，繼續在西班牙沿岸進行他的游擊戰。此年9月，他在Tlemcen又一次打敗西班牙的進攻。
1536年，海雷丁被召回伊斯坦布爾接受命令，進攻那不勒斯的哈勃斯堡王國。翌年7月，他在奧特蘭託登陸並佔領該城，隨後攻佔了幾座城堡。同年8月，海雷丁與人攻佔了威尼斯共和國的愛琴海及愛奧尼亞所屬島嶼。威尼斯向教皇保羅三世要求組織“神聖同盟”以對抗土耳其。
1538 年2月，教皇果然成立神聖同盟，成員有教皇領、威尼斯、神聖羅馬帝國、西班牙及馬耳他騎士團。此年9月，神聖同盟聯合艦隊由安德魯率領，與海雷丁在希臘的普雷維薩灣附近交戰，結果海雷丁取得勝利。這場勝利也奠定了土耳其今後33年間在整個東西地中海的霸權地位。盛極一時的威尼斯共和國從此一蹶不振，歷史悠久的絲綢之路也被切斷，直到1571年的勒班陀海戰才改變局面。
從1539年夏天開始，海雷丁不斷蠶食、騷擾威尼斯領土，迫使其在1540年10月與奧斯曼土耳其簽訂和平協議，承認土耳其所獲取的領土，並賠償30萬金幣。
1540 年9月，查理五世聯繫到海雷丁，試圖收買他，但遭到拒絕。既不能拉攏海雷丁，又想在西地中海結束海盜對西班牙領土及基督徒的威脅，查理五世於1541年 10月決定興兵圍攻阿爾及爾。但這個季節並不適合作戰，安德魯苦勸未果，結果在登陸時，一場暴風雨讓許多西班牙艦船擱淺。在匆匆交手幾回合後，查理五世不得不放棄這次行動。
1543年，海雷丁前往馬賽協助奧斯曼盟友法國。在通過墨西拿海峽時，他要求卡拉布利亞的長官投降。對方以炮火作爲迴應，並殺了他的3名水手。憤怒的海雷丁圍攻並佔領該城，進而攻擊羅馬。法國此時卻支持羅馬。於是海雷丁於8月5日佔領了尼斯，並在土倫和他的3萬名部下過了一個冬天，其間時不時騷擾一下西班牙，還把土倫的聖瑪麗教堂改成一座清真寺。當時，奧斯曼的貨幣可以在當地流通。
1544年至1545年是海雷丁最後的海軍與海盜生涯。其間他又與西班牙打了幾仗，只在1544年查理五世與蘇萊曼達成和平協議的時候歇了一陣。
儘管阿拉伯和土耳其的史書竭力將海雷丁樹立爲正統的海軍英雄，但公正地說，他就是海盜。他後來雖然統率奧斯曼大軍，高居帝國元勳之位，但一直沒有放棄以劫掠補給的海盜傳統，甚至把劫掠的財寶定期送給奧斯曼蘇丹。他曾爲得到一名叫茱莉亞的那不勒斯貴婦，竟洗劫了意大利南部小城桑塔露琪亞;他也曾以屠城相威脅，強迫西西里雷喬城長官將幼女嫁給他。
1545年，已經打了50餘年仗(指揮大小戰爭數百次，幾乎從未失手、失敗過)、縱橫馳騁地中海一輩子、年逾 80歲高齡的海雷丁在伊斯坦布爾退役。他兒子成了他在阿爾及爾的繼承者。有人根據其口述寫成五卷《海雷丁回憶錄》，現存於土耳其託普卡匹皇宮與伊斯坦布爾大學圖書館。
翌年，海雷丁在伊斯坦布爾去世。他的陵寢位於博斯普魯斯海峽的金角灣。每一艘經過此處的土耳其船隻都會降帆鳴號，向他致敬。這是世界海盜史上空前絕後的殊榮。
海雷丁死後，海盜內部一度不穩，最終未能保住他們在北非的世襲領地。隨着土耳其勢力的退縮，海盜們也漸漸變成真正的官員、官兵，自此從大海上消失了。
