Argel se convirtió en el refugio de Barbarroja cuando éste tuvo que huir de Túnez para salvar su vida de los furiosos cristianos. Allí puso todo su empeño en reorganizar la flota otomana y, de nuevo, tomar la represalia, pues había sido vencido y humillado por sus grandes enemigos.
Barbarroja fue llamado a Estambul por el sultán Solimán el Magnífico. Salió armado con una gran flota, porque, por supuesto, no se dirigía directamente a la capital del Imperio otomano, sino que primero fue a vengarse del rey español atacando las Baleares. Hayreddín ordenó a sus marinos que se vistiesen de cristianos y que hiciesen lo mismo con las galeras; de este modo, cuando atracaron en el puerto de Mahon (Menorca), los habitantes pensaron que era la victoriosa armada imperial y no se protegieron de su llegada.
Las fuentes cuentan que el gobernador de la isla, Mosen Oliver, quedó fuera de la ciudad cuando Barbarroja la cercó y no sabía cómo entrar para poder avisar a sus ciudadanos del inesperado ataque. En el mejor momento un bandolero menorquín se ofreció a penetrar en la ciudad y avisar a la población si le retiraban la pena, a lo cual el gobernador aceptó; los habitantes fueron avisados de la farsa y comenzaron a defenderse. A pesar de esto, Barbarroja y sus hombres se llevaron todo lo que pudieron y más, pues incluso robaron las aldabas y cerrojos de las puertas. El caso de Mahon es sólo un ejemplo de tantos puertos que fueron destruidos y saqueados por la flota otomana, pues, durante meses, Hayreddín se dedicó a obtener el máximo botín posible para consumar su venganza.
En 1536 el pirata llegó a Estambul y el sultán le encargó tomar el mando del ataque naval otomano contra el Reino de Nápoles de los Habsburgo. Un año después, Barbarroja captura las ciudades italianas de Otranto y Ugento, y la fortaleza de Castro.
La expansión del Imperio otomano provocó una crisis económica en la República de Venecia, que se ve incapaz de continuar la guerra contra el infiel. La primera solucion que llevó a cabo fue firmar un pacto con los turcos en el año 1538, pero Barbarroja rompió el acuerdo, ya que siguió atacando por mar; incluso se vengó de los venecianos atacando sus islas egeas y jónicas, arrebatándoles Corfú (Grecia) e incursionando en Calabria (Italia). La segunda medida que tomó Venecia fue aliarse con el Papa Pablo III y con Carlos I de España contra Solimán. Las naves venecianas, dirigidas por el capitan Domingo Capello, las papales, capitaneadas por Marco Grimano, junto con las imperiales, comandadas por Andrea Doria y don Fernando de Gonzaga, formaron la Liga Santa. Es una de las mayores movilizaciones armadas del siglo XVI, con lo que podemos llegar a entender lo hartos y desesperados que estaban los cristianos por deshacerse de los turcos. La enorme flota cristiana fue en búsqueda de Barbarroja, que se encontraba en Preveza (Grecia).
La Batalla de Preveza (1538) será recordada como uno de los episodios más vergonzosos de los cristianos. La armada de la Liga Santa contaba con unos 300 barcos y 60.000 soldados, frente a los 122 barcos y 20.000 soldados del Imperio otomano. Las condiciones climatológicas fueron adversas, lo que dificultó el ataque cristiano, pero, según otras fuentes, la derrota se debió a una mala estrategia: Andrea Doria estaba dentro de la bahía de Preveza y permaneció allí demasiado tiempo, pues la flota otomana estaba ya muy próxima; la salida fue dificultosa y el despliegue no era fácil, lo que aprovechó el pirata turco para realizar un ataque rápido y destructivo. Por tanto, a pesar de la clara desventaja numérica de la flota de Barbarroja, Doria acabó por dar la orden de retirada.
Durante 33 años el Mediterráneo sería un mar turco (hasta la Batalla de Lepanto en 1571).
Andrea Doria, un año después, quiso tomar la revancha conquistando la ciudad de Castilnovo (en la costa de Dalmacia, Croacia), pero Solimán mandó a tiempo a Barbarroja, que acabó expulsando al almirante genovés. Hayreddín capturó algunas ciudades griegas como Skíathos, Andros y Serifos. También el castillo de Risan, la fortaleza veneciana de Cattaro y la española de Santa Veneranda. Finalmente regresó a Estambul.
La República de Venecia, sintiéndose derrotada tras el fracaso de Preveza, firma un tratado de paz con Solimán en 1540, con el cual reconocen las conquistas turcas y pagan 300.000 ducados de oro.
En 1541 Carlos I decidió, tras regresar de visitar a los reyes de Alemania y Francia, repetir la experiencia de Túnez atacando Argel. Otras fuentes cuentan que el rey español mantuvo conversaciones secretas con Barbarroja para que abandonara al sultán, otorgándole el cargo de almirante jefe de su flota y el gobierno del Norte de África, pero el pirata rechazó su oferta. Entonces, Carlos I, enfadado, decidió conquistar Argel. Lo primero que hizo el rey fue escribir a los capitanes Duque de Alba y don Bernardino de Mendoza para que prepararan la armada. Debido a una deficiente planificación, la expedición se retrasó hasta principios de otoño; sus hombres de confianza intentaron disuadirlo, porque no era la temporada más idónea para una guerra, pero Carlos siguió adelante. Así, cuando el rey español desembarcó en la ciudad de Argel, unas tormentas dispersaron la flota y la lucha por tierra tampoco tuvo mucho éxito. El monarca tuvo que huir dejándose en esa guerra muchos hombres, embarcaciones, dinero y prestigio.
A partir de este estrepitoso fracaso Carlos I se irá desentendiendo de los asuntos de Berbería y se centrará en el centro de Europa, que también estaba amenazado por los otomanos.