Hij begon zijn marinecarrière als een barbarijse piraat, samen met zijn broers, christelijke kustdorpen overvallen en schepen over de Middellandse Zee in beslag nemend. Khair-ed-Din, ook bekend als Hayreddin Barbarossa, was zo succesvol als een zeerover dat hij erin slaagde de heerser van Algiers te worden, en vervolgens de admiraal van de Ottomaanse Turkse marine onder Suleiman de Magnifieke. Barbarossa begon zijn leven als zoon van een eenvoudige pottenbakker en groeide uit tot blijvende piratenbekendheid.
Khair-ed-Din werd ergens eind 1470s of vroege 1480s geboren in het dorp Palaiokipos, op het Ottomaanse gecontroleerde eiland Midilli. Zijn moeder Katerina was waarschijnlijk een Griekse christen, terwijl zijn vader Yakup van onzekere etniciteit is - verschillende bronnen beweren dat hij Turks, Grieks of Albanees was. In ieder geval was Khair de derde van hun vier zonen.
Yakup was een pottenbakker, die een boot kocht om hem te helpen zijn goederen over het hele eiland en daarbuiten te verkopen. Zijn zonen leerden allemaal zeilen als onderdeel van het familiebedrijf. Als jonge mannen bedienden zonen Ilyas en Aruj de boot van hun vader, terwijl Khair een eigen schip kocht; ze begonnen allemaal te opereren als kapiteins in de Middellandse Zee.
Tussen 1504 en 1510 gebruikte Aruj zijn vloot van schepen om Moorse moslimvluchtelingen van Spanje naar Noord-Afrika te helpen na de christen Reconquista en de val van Granada. De vluchtelingen noemden hem Baba Aruj of 'Vader Aruj', maar christenen hoorden de naam als Barbarossa, dat is Italiaans voor 'Redbeard'. Trouwens, Aruj en Khair hadden allebei rode baarden, dus de westerse bijnaam bleef hangen.
In 1516 leidden Khair en zijn oudere broer Aruj een zee- en landinvasie van Algiers, vervolgens onder Spaanse overheersing. De plaatselijke amir, Salim al-Tumi, had hen uitgenodigd om zijn stad te komen bevrijden, met hulp van het Ottomaanse rijk. De broers versloegen de Spanjaarden en verdreven hen uit de stad, en vermoordden vervolgens de amir.
Aruj nam de macht over als de nieuwe Sultan van Algiers, maar zijn positie was niet veilig. Hij aanvaardde een aanbod van de Ottomaanse sultan Selim I om Algiers deel uit te laten maken van het Ottomaanse rijk; Aruj werd de Bey van Algiers, een zijrivier onder de controle van Istanbul. De Spanjaarden vermoordden Aruj in 1518 bij de verovering van Tlemcen en Khair nam zowel het beyship van Algiers als de bijnaam "Barbarossa" over.
In 1520 stierf Sultan Selim I en een nieuwe sultan nam de Ottomaanse troon. Hij was Suleiman, door Europeanen "The Lawgiver" genoemd en "The Magnificent". In ruil voor Ottomaanse bescherming uit Spanje bood Barbarossa Suleiman het gebruik van zijn piratenvloot aan. De nieuwe bey was een organisatorisch brein en al snel was Algiers het centrum van de privé-activiteit voor heel Noord-Afrika. Barbarossa werd de de facto heerser van alle zogenaamde Barbary-piraten en begon ook een aanzienlijk landgebaseerd leger op te bouwen.
Barbarossa's vloot veroverde een aantal Spaanse schepen die met goud beladen terugkomen uit Amerika. Het overviel ook kustgebieden Spanje, Italië en Frankrijk, voerde buit uit en ook christenen die als slaven zouden worden verkocht. In 1522 hielpen Barbarossa's schepen bij de Ottomaanse verovering van het eiland Rhodos, dat een bolwerk was geweest voor de lastige ridders van St. John, ook wel Knights Hospitaller genoemd, een bevel overgebleven van de kruistochten. In de herfst van 1529 hielp Barbarossa nog eens 70.000 Moren te vluchten uit Andalusië, Zuid-Spanje, dat zich in de greep van de Spaanse inquisitie bevond.
Gedurende de jaren 1530 bleef Barbarossa de christelijke scheepvaart veroveren, steden innemen en christelijke nederzettingen rond de Middellandse Zee aanvallen. In 1534 zeilden zijn schepen tot aan de rivier de Tiber en veroorzaakten paniek in Rome.
Om de dreiging die hij vormde te beantwoorden, stelde Karel V van het Heilige Roomse Rijk de beroemde Genuese admiraal Andrea Doria aan, die Ottomaanse steden langs de Zuid-Griekse kust begon te veroveren. Barbarossa reageerde in 1537 door een aantal door Venetië gecontroleerde eilanden in beslag te nemen voor Istanbul.
De gebeurtenissen kwamen tot een hoogtepunt in 1538. Paus Paulus III organiseerde een 'Heilige Liga' bestaande uit de pauselijke staten, Spanje, de ridders van Malta en de republieken Genua en Venetië. Samen verzamelden ze een vloot van 157 galeien onder het bevel van Andrea Doria, met de missie om Barbarossa en de Ottomaanse vloot te verslaan. Barbarossa had slechts 122 galeien toen de twee troepen samenkwamen op Preveza.
De Slag om Preveza, op 28 september 1538, was een verpletterende overwinning voor Hayreddin Barbarossa. Ondanks hun kleinere aantallen nam de Ottomaanse vloot het offensief en stortte neer door Doria's poging tot omsingeling. De Ottomanen zonken tien schepen van de Heilige Liga, veroverden er nog 36 en verbrandden drie, zonder zelf een schip te verliezen. Ze vingen ook ongeveer 3.000 christelijke zeelieden, ten koste van 400 Turkse doden en 800 gewonden. De volgende dag beval Doria, ondanks aandringen van de andere kapiteins om te blijven en te vechten, de overlevenden van de vloot van de Heilige Liga om zich terug te trekken.
Barbarossa ging verder naar Istanbul, waar Suleiman hem ontving in het Topkapi-paleis en hem promoveerde naar Kapudan-i Derya of "Grand Admiral" van de Ottomaanse marine, en Beylerbey of "gouverneur van gouverneurs" van Ottomaans Noord-Afrika. Suleiman gaf Barbarossa ook het gouverneurschap van Rhodos, passend genoeg.
De overwinning in Preveza gaf het Ottomaanse Rijk dominantie in de Middellandse Zee die meer dan dertig jaar duurde. Barbarossa profiteerde van die dominantie om alle eilanden in de Egeïsche en Ionische Zeeën van christelijke vestingwerken te ontdoen. Venetië klaagde voor vrede in oktober 1540, erkende Ottomaanse suzerainty over die landen en betaalde oorlogsvergoedingen.
De Heilige Romeinse keizer, Karel V, probeerde in 1540 Barbarossa te verleiden om de beste admiraal van zijn vloot te worden, maar Barbarossa was niet bereid om geworven te worden. Charles leidde de volgende herfst persoonlijk een belegering op Algiers, maar stormachtig weer en de formidabele verdedigingswerken van Barbarossa verwoestten de heilige Romeinse vloot en stuurden hen naar huis. Deze aanval op zijn thuisbasis bracht Barbarossa ertoe om een nog agressievere houding aan te nemen, door de westelijke Middellandse Zee aan te vallen. Het Ottomaanse rijk was tegen die tijd verbonden met Frankrijk, in wat de andere christelijke naties 'The Unholy Alliance' noemden, in tegenstelling tot Spanje en het Heilige Roomse Rijk.