奧羅不甘心就此放棄海上生涯和為弟弟複仇，試圖東山再起，他先後獲得了土爾其王子和馬穆魯克蘇丹的賞識並獲得船隻支持。1503年，海雷丁決定把自己的船隊與哥哥合並，共同進退。
1504年，兄弟倆獲得北非蘇丹的準許，以突尼斯港口拉古萊特作為基地進行海盜活動，所得的三分之一歸蘇丹所有。於是不少來自教皇領地的船遭了秧，甚至一艘西西裏的軍艦也被他們俘虜了，上麵滿載著來自阿拉貢的380名西班牙士兵和60名騎士。隨後，奧羅兄弟幹了一件驚天動地的事：洗劫了羅馬教皇兩艘滿載藝術品和財物的大型戰船，並在北非沿岸招搖過市，此舉讓他們成為阿拉伯人的英雄，卻變成基督教世界的公敵。
1505年，奧羅兄弟襲擊了意大利的卡拉布裏亞海岸。這些成就讓他們名聲大噪，許多有名的伊斯蘭海盜紛紛加入麾下。1508年，他們又突襲了意大利的蔚藍海岸。1509年，四兄弟的老大以撒克也加入了他們的團夥。
同時，從1504年到1510年這6年間，奧羅兄弟率領艦隊把許多穆斯林從西班牙撤回了北非，讓他們免於受到西班牙帝國的壓迫。這一舉動讓奧羅獲得了很高的名望，人們送給他一個尊稱“BabaOru”，意思就是“像父親一樣的奧羅”。不過，這個名稱在歐洲大陸變成了“Barbarossa”，也就是著名的神聖羅馬帝國皇帝菲特烈（他也是個紅胡子）的綽號。所以早期的巴巴羅薩主要是指老二奧羅，海雷丁成為巴巴羅薩是後來的事了。
這時候，強大的西班牙人開始染指北非，他們采用了避重就輕的戰略，聰明地避免海上交鋒，而是從陸地上攻占了奧蘭、阿爾及爾等多個海盜據點，把巴巴羅薩的海盜團包圍住，限製了他們的活動。到了1516年，西班牙國王一去世，巴巴羅薩就趁機卷土重來，占領了阿爾及爾。世界史上絕無僅有的海盜王國——巴巴羅薩王朝誕生了。當時因為奧斯曼帝國派人索要賦稅和貢品，巴巴羅薩一氣之下，一度與土耳其斷交。
西班牙人當然不能容忍一個卑賤的海盜頭子挑戰他們的權威，他們聯合馬耳他騎士團，對巴巴羅薩海盜團夥展開圍剿。1518年8月17日，雙方在阿爾及爾激戰。西班牙人在史書上記載，紅胡子海盜巴巴羅薩在阿爾及爾之戰中已經被西班牙貴族卡瑪·雷斯利殺死了；而阿拉伯人的史書卻堅稱，勇猛的海盜王突出了重圍，全身而退，並重新回歸土耳其奧斯曼帝國。這一懸案至今爭議不絕，也有人認為，巴巴羅薩的確在此役戰死，也就是老二奧羅，而後麵那個複活的海盜王，其實是他最有能力的兄弟海雷丁。
不管雙方如何說，海盜王巴巴羅薩最終又出現在人們的麵前，奧斯曼帝國贈給他精兵2000，他本人又號召了4000水手，在那個時代，如此龐大的兵力已儼然一個強國了。巴巴羅薩繼續殘酷無情地對西班牙各港口實施洗劫，甚至比以前更為殘暴，他掠奪財富、人口，實行焦土政策，留下了“魔鬼海盜”的罵名。
在1529年，巴巴羅薩立誌攻下了阿爾及爾港口的孤島佩農要塞（這個要塞西班牙人堅守了29年），他用買來的幾百門重炮連轟了要塞6個晝夜。占領佩農後，阿爾及爾不攻自破。巴巴羅薩在阿爾及爾建立起了國家規模的海盜統治地位，沒有遇到強有力的反抗。
由於巴巴羅薩所建立的“豐功偉績”，在1533年奧斯曼帝國計劃進攻維也納時，奧斯曼帝國蘇萊曼大帝在君士坦丁堡（現在的伊斯坦布爾）封海雷丁為帝國海軍元帥，授權其指揮全部帝國艦隊，並宣布：“我把所有船隻交你指揮，把帝國的海岸托你保衛。”
第二年，巴巴羅薩就指揮海軍將西班牙人全部逐出了北非。被激怒的西班牙皇帝查理五世派出海軍名將安德魯維·多利亞出戰，但在1538年9月的普雷維薩灣海戰中巴巴羅薩大敗多利亞。這場大戰後，盛極一時的威尼斯共和國一蹶不振，被迫與蘇萊曼大帝簽訂了不平等條約。土耳其完全控製了東地中海，曆史悠久的絲綢之路從此被切斷了，而巴巴羅薩成了地中海權利無限的霸主。
阿拉伯人和土耳其人把巴巴羅薩看做是自己的海軍英雄，他們的史書也竭力想證明這一點。但從事實來看，他就是海盜。巴巴羅薩後來統率奧斯曼大軍，但一直沒放棄以劫掠補給的海盜傳統，甚至把劫掠的財寶定期送給奧斯曼皇帝。他也是個為了愛情不顧一切的人，為了得到一名叫茱莉亞的那不勒斯貴婦，他曾洗劫意大利南部小城桑塔露琪亞；他為了娶得心儀的美女，也曾以屠城相威脅，強迫西西裏雷喬城長官將幼女嫁給他。
1546年7月4日，海雷丁在伊斯坦布爾去世，他的陵寢位於博斯普魯斯海峽的金角灣，每一艘經過此處的土耳其船隻都會降帆鳴號，向他致敬，這是世界海盜史上空前絕後的殊榮。