Кануни Султан Сулейман, призвав в Стамбул, «бейлербея» Алжира Барбарос Хайреттин Пашу, открывает новую страницу в средиземноморской политике. Прибывший, 27 декабря 1533 года, в Стамбул из Алжира, с сильным флотом и восемнадцатью своими адмиралами, Барбарос Хайреттин Паша, 16 апреля 1534 года, назначается Каптан-и Дерья (адмиралом флота) Османской Империи. После чего, 22 августа 1534 года, Барбарос завоевывает Тунис, но уже через год, 21 июля 1535 года, король – император Чарльз Квинн, лично командуя войсками, отвоевывает Тунис у турков. Северная часть Туниса осталась у арабов, находившихся под властью испанцев, а средняя и южная части остаются у османцев. Однако, Барбарос и его адмиралы, не прекращают свои нападения на Испанию и принадлежащие ей земли юга Италии. В августе 1535 года, Барбарос идет на Болеарские острова, в 1537 году на Италию, захватывает у Венеции Кикландские о-ва. Чарльз Квинн, поняв, что если он не уничтожит турецкие силы на Средиземном море, то проиграет партию, собирает со всей Европы, самую большую армаду, того времени и отправляет ее под руководством известного и опытного в морских боях Андреа Дориа, против турецкого флота. 28 сентября 1538 года, обе флотилии встречаются в открытом море, вблизи Превезе. В морском сражении, в котором участвовало более 120тыс. человек, Барбарос тактическими маневрами, нанес сильное поражение флоту европейцев.
Чарльз, желая отомстить Барбаросу за недавнее поражение, высаживает войска с кораблей Андреа Дореа, уцелевших после боя, в Алжир, но Барбаросзаде Хусеин Бей, 24 октября 1541 года в бою, в котором самому Чарльзу чудом удается избежать смерти, разбивает войска Чарльза и его адмирала. Летом 1543 года, Барбарос, захватывает принадлежащую Чарльзу, Ниццу и зиму 1543- 1544 года, проводит в Тулоне. Таким образом, Чарльз Квинн, теряет надежду на подавление, своего самого большого конкурента в Европе – Франции. 4 июля 1546 года, Барбарос, в уважении и величии, умирает в Стамбуле, оставив после себя много талантливых учеников.
Его сыновья, Хасан Паша, Хакан Паша и друг Барбароса Салих Паша, как «бейлербеи» Алжира, сделали много для величия Османской Империи в Северной Африке. Сильный флот Алжирского бейлербейлика, под управлением этих адмиралов, взял под свою власть, все западное средиземноморье и много раз ходили в Атлантику. В это время Салих Паша, если и временно, присоединяет Арабскую Империю Марокко к Османской Империи (с 22 сентября 1551 года по июнь 1556 года). Таким образом, власть османцев достигла Атлантического Океана. Занявшие юг Гибралтара османцы, оставили испанцам несколько баз, которые они удерживали с большими потерями. В этот же период, Барбаросзаде Хасан Паша, 5 сентября 1558 года, во время своего второго правления Алжиром, наносит сильнейшее поражение испанцам, близь Мостаганема.
Самый талантливый ученик Барбароса - Тургут Реис, после завоевания среднего и южного Туниса и гениально проведенной игры на острове Джебре, против Андреа Дориа, в июле 1551 года, высаживает войска на Мальту. 15 августа, того же года, захватывает Триполи, бывший, под властью рыцарского ордена Сен- Джона (Saint-Jean) и после победы в Понзенском морском сражении 5 августа 1552 года, через год, 17 августа 1552 года, захватывает всю территорию острова Корсика.