A partir de 1533, Barbarroja se puso al servicio del sultán turco Solimán el Magnífico. Una de las fuentes cuenta que Hayreddín deseaba servir al nuevo sultán para conseguir su protección, pues temía al almirante Andrea Doria, a pesar de que lo había derrotado. El pirata le mandaba cartas hasta que Solimán le contestó invitándole a Estambul, antigua Constantinopla, en 1533. Pero, según otra fuente, el sultán otomano se vio agobiado por los ataques de Doria y pensó que sería conveniente tener a un poderoso almirante bajo su mandato. Y, cuando alguien es convocado por el sultán, es mejor asegurarse una buena relación con él, por lo que Hayreddín embarcó hacia Estambul con presentes y esclavos de sobra.
La historia cuenta que, cuando Barbarroja llegó a la capital del Imperio otomano, el sultán estaba ausente y el pirata tuvo que esperarlo en su nave, a pesar de que él se esperaba una gran fiesta en su honor. Viendo que Solimán tardaba, partió a buscarlo para decirle lo mal que había sido tratado en Estambul. Barbarroja regresó a la ciudad con una carta del sultán obligando a sus siervos a que trataran al pirata como a un rey.
Cuando Solimán I se presentó en la capital nombró a Hayreddín Barbarroja “capitán general del mar y de todas sus flotas”, es decir, almirante jefe de la armada otomana (Kapan-i Derva o Kapudán Bajá). Tambien le dio el título honorifico de Baba Oruç o Baylar Bey (jefe gobernador o comandante general), dándole el gobierno de algunas provincias del mar Egeo, así como Argel. Otras fuentes, sin embargo, hablan de la grandiosa entrada del pirata en Estambul y su buena acogida.
Desde entonces, Barbarroja establece las bases de su actuación en dos frentes: hostilidad continua a las tierras cristianas, en especial la España de Carlos I, y proteccion del sultán Solimán el Magnífico.
En un tiempo record Barbarroja creó una enorme armada con las pautas de la piratería argelina. La principal característica de esta flota era que estaba formada por galeras más pequeñas, más ágiles y mejor maniobrables, frente a las de las potencias cristianas, que eran grandes y pesadas. Barbarroja pretendía crear una flota más profesional, con una tripulación más entrenada, por lo que, como colaboradores, utilizó a cristianos e italianos renegados, sustituyendo a los anteriores griegos y turcos poco preparados. Esta nueva armada dirigida por Barbarroja garantizará el dominio turco del mediterráneo durante los siguientes 40 años.
Francisco I, rey de Francia, necesitaba ayuda con Génova en esta época, por lo que intentó que Barbarroja se cambiara de bando. A pesar del rechazo del pirata, el sultán Solimán y Francisco I tenían algo en común: la enemistad con Carlos I de España, por lo que ambos reyes sellan una alianza. Hayreddín, entonces, se dirigió a Génova para conquistarla en nombre del rey francés.
Barbarroja, ansioso por probar su nueva flota, lleva a cabo en 1534 una de las más terribles incursiones corsarias (raids) sobre Italia. Arrasó las costas de Sicilia, Cerdeña, la Toscana, Campania y Calabria; incursionó en algunas islas italianas como Elba, Capri, Procida o Ponza; y bombardeó puertos como los de Cetraro, Nápoles u Ostia. Ocurrió que cuando Barbarroja atacó el puerto de Ostia las campanas de las iglesias de Roma sonaron para avisar del peligro de la invasión islámica; algunos cardenales pensaron que la ciudad era el objetivo del pirata, por lo que la abandonaron buscando lugares más seguros.
Como curiosidad está la historia de Giulia Gonzaga: Hayreddín quería atacar la ciudad de Fondi (ciudad italiana del interior) para capturar a Giulia Gonzaga, famosa por su belleza, y entregársela al sultán; por suerte, según cuentan las fuentes, la joven escapó. A pesar de esto, Barbarroja arrasó la ciudad y esclavizó a toda la población.
Barbarroja y su flota salieron victoriosos en su batalla contra la Cristiandad, además de obtener tal botín en riquezas y esclavos que no sabían ya dónde meterlos.
Con la excusa de arreglar cuentas con el sultán de Túnez, Muley Hassán, el pirata se dispuso a entrar en el país. Pero, en realidad, su viaje devastador por Italia finalizará con una ofensiva contra Túnez, ataque pactado ya con Solimán. En 1534, en tan sólo dos días, conquistó Túnez, el mejor puerto de la costa de Berbería y centro del Mediterráneo; también tomó Cartago y la fortaleza de La Goleta, situada en la entrada de la laguna salada en cuya orilla se encontraba Túnez.
Muley Hassán huyó de la ciudad y pidió ayuda al rey Carlos, el cual, harto de la tiranería marítima del pirata, pensó que había llegado el momento de intervenir.