За пізнього середньовіччя, коли політична ситуація змінилася, відродилися піратські осередки на узбережжі Північної Африки. Найбільшою силою в ісламському світі була на той час Оттоманська Порта, якій у Середземному морі протистояли флоти Іспанії, Франції та італійських республік. У Північній Африці утворилися невеличкі феодальні держави, якими правили місцеві династії, підтримувані Туреччиною. Там, де розкинулася територія Магрібу аль-Акси (по-арабському це означає «найдальший захід»), кілька століть поспіль існували республіки піратів, яких називали берберійськими, хоча й не бербери (корінні мешканці Магрібу) відігравали в них провідну роль.

У кінці XV століття іспанські араби, яких прозивали маврами, були витіснені християнами в Африку. Ті, хто не зміг влаштуватися в Магрібі і палав ненавистю до іспанців, подалися в море. Тим більше, що маври добре знали своє донедавна рідне узбережжя Піренейського півострова.

Дехто з вигнанців мав гроші. Вони спорядили кораблі, і знову розгорілося полум'я «священної війни».

Але тепер ситуація змінилася. Християни уже навчилися давати відсіч, використовуючи як бази острови, захоплені європейськими державами: Балеарські, Сицилію, Корсику, Сардинію, Мальту. Звідти у море вирушали кораблі і грабували мусульманські торговельні судна, спустошували магрібські береги.

Піратство стає взаємним.

Варто зазначити, що деякі пірати-християни майже не звертали уваги на релігійну приналежність жертви. Морських розбійників Майорки однаково боялися як християни, так і мусульмани. Траплялося, що сицилійські та катадонські корсари повністю блокували морську торгівлю в Адріатиці.

Після кожного мавританського наскоку іспанські та португальські королівські двори організовували каральні експедиції на узбережжя Північної Африки і в глиб суходолу. 1399 року іспанці дійшли до Тетуани і знищили місто і все його населення, за винятком працездатних чоловіків, яких обернули на рабів. 1415 року португальці зробили те ж саме в Сеуті, 1471 року — в Танжері. Але всі ці операції не зменшили полум'я піратського газавату. Його підживила ще одна подія, яка відбулася на протилежному березі Середземного моря: 1453 року під ударами турків-османів упала християнська твердиня — Константинополь.

XVI століття було бурхливою добою для Північної Африки. На її узбережжі утворилися великі піратські бази, які пізніше набули державних форм і стали осередками турецької колонізації.

Помітну роль у цьому процесі відіграли, як не дивно, не корінні мусульмани, а, так би мовити, навернуті — два бра-ти-греки.

… Улітку 1504 року дві добре озброєні галери, які належали до папського флоту, пропливаючи біля острова Ельба, здибали чужий корабель. Капітан передньої галери Паоло Віктор, не сподіваючись на присутність піратів у цьому районі, бойову готовність не оголошував. Але коли кораблі зблизилися, італійці помітили, що на щоглі чужинця майорить прапор з півмісяцем. Повертати було запізно, і довелося ставати до бою. Кораблі зчепилися, й пірати кинулися на абордаж. Невдовзі екіпаж папської галери, добре проріджений кривими широкими шаблями нападників, зайняв лавки галерників.

Але це виявився не останній успіх піратів. Вони перевбралися в одяг італійців, захопили їхню зброю і кинулися наздоганяти другу галеру, яка не підозрювала про небезпеку. Підступ удався. Через кілька днів мешканці Туніса спостерігали, як у порт входив піратський корабель, буксируючи за собою дві галери, повні полонених.

Так розпочав свою кар'єру організатор берберійського піратства Аруй (Хорук) Рудобородий (Барбаросса). Разом з братом він прибув на африканське узбережжя з острова Лесбос, що в Егейському морі. Брати походили з християнської родини грецького гончаря, але ще в дитинстві, після того, як островом оволоділи турки, прийняли іслам. У юності вони займалися морським розбоєм в Егейському морі, але з часом його акваторія видалася затісною для їхніх амбіцій, до того ж вона була надто близько від центру імперії. Отож, вирушили на захід, в напрямку міст і шляхів, часто відвідуваних «невірними». Своєю базою спочатку обрали острів Джерба, пізніше перебралися до Тунісу, правитель якого охоче їх прихистив за п'яту частину здобичі.

Сила Рудобородого швидко зростала, і через кілька років після прибуття на африканське узбережжя він здобуває Алжир (1510 рік) і влаштовує там свою головну резиденцію. Аруй Рудобородий загинув під час пізніших боїв з іспанцями на суходолі, прикриваючи відхід своїх товаришів після поразки під Тлемсно у 1518 році.

Владу перебрав його брат, Хайр ад-Дін, відомий серед християн теж як Барбаросса, хоча, як свідчать письмові джерела, у нього була не руда борода. Він підфарбовував її хною, щоб підтримувати родинну традицію. З самого початку свого командування піратами ад-Дін цілком добровільно вчинив те, чого уникав його старший брат. Він прийняв підданство султана Туреччини й дістав за це титул бейлер-бея (бея над беями) і під свою оруду тисячу (інші джерела свідчать, що дві, навіть чотири тисячі) яничарів, які стали його гвардією.

Під новим керівництвом пірати з подвійною енергією рушили в бій і захопили нарешті іспанську фортецю на острові Пеньйон, яка блокувала вхід до алжирського порту. Нечисленні, відрізані від постачання захисники фортеці довго не боронилися. Її коменданта Мартіна де Варгаса привезли в місто і забили насмерть батогами на центральному майдані Алжира. Фортечні мури розібрали християнські невільники і з добутого таким чином каменю виклали портову набережну, яка збереглася донині.

Піратські кораблі сіяли страх, доходячи до Адріатики і грабуючи там маєтності найбагатшої італійської республіки Венеції. 1534 року флот Хайр ад-Діна, що мав у своєму складі 60 галер, несподівано атакував Реджіо в Мессінській протоці. Головною метою була славна своєю вродою княжна Траєтто — Юлія Гонзага. Пірат хотів її подарувати Сулейманові Пишному, щоб завоювати більшу прихильність султана. Але Юлію попередили, і вона в останню мить утекла.

Розгніваний пірат віддав місто на розграбування своїм поплічникам. Занепокоєні активністю розбійників іспанці організували проти них черговий похід. У Барселоні було сформовано флот із 600 кораблів, яким командував генуезець на іспанській службі Андреа Доріа. 1536 року іспанці за участю мальтійських лицарів захопили Туніс, незважаючи на шалені контратаки одного з капітанів ад-Діна — Сінана Єврея. Переможці-християни влаштували «карнавал смерті». Кілька днів вони плюндрували місто і мордували його мешканців, хоча в основному це були мирні жителі.

Самі пірати, втікши з міста, затаїлися за мисом Боне. Звідтіля вони попливли в напрямку Балеарських островів. Жителі Мінорки, вважаючи, що це повертається з переможного походу іспанський флот, скупчилися на березі… Як і передбачав ад-Дін, несподіванка була цілковитою. Пірати взяли в полон шість тисяч чоловік і відіслали їх до Стамбула. Мабуть, подарунок сподобався Сулейманові, бо Хайр ад-Дін дістав звання головного адмірала турецького флоту.

Кількома роками пізніше (1538) турецький флот, якому допомагали берберійські пірати, завдав відчутної поразки християнам у битві під Превезою (Іонійське море). Це забезпечило на кілька десятків років турецьке панування на Середземному морі. На цю битву християнське воїнство спорядило 80 венеціанських, 36 папських, 30 іспанських галер, а також 15 галеонів. Загалом на суднах зібралося близько 60 тисяч чоловік. Але доля не всміхнулася християнам. Насамперед нібито через бездарність адмірала Андреа Доріа і бурю, що розігралася наприкінці битви. (Щодо Андреа Доріа свідчення сучасників суперечливі. Інші стверджують, що це був досвідчений і обачливий флотоводець).

1541 року Доріа організував новий похід. У ньому взяло участь 12 тисяч солдатів і 500 кораблів. Метою походу було здобуття Алжира. Але справі перешкодили осінні шторми. Іспанський флот був розпорошений і пристав до берега невеликими групами. Несподіваний напад піратів на одну з них закінчився розгромом відділу мальтійських лицарів, які теж брали участь у поході. З експедиції повернулося заледве чотири тисячі чоловік. Більшість уцілілих потрапили в полон. З того часу християни стали називати Алжир «Томбо де Шевальє» — могилою лицарів.