XV в., как мы видели, стал свидетелем двух катаклизмов, произошедших по разные стороны Средиземного моря: падения Константинополя на Востоке в 1453 г. (в результате Черное море оказалось закрыто для кораблей христиан) и постепенное изгнание мавров из Испании на западе в период начиная с 1492 г. Оба привели к быстрому увеличению числа бездомных бродяг (на Востоке — христиан, на Западе — мусульман); разоренные, недовольные, они жаждали мщения, и многие из них начали вести жизнь пиратов. Обычно христиане базировались в Центральном Средиземноморье: на Сицилии, Мальте или на одном из бесчисленных островов близ побережья Далмации. В свою очередь, мусульмане могли только присоединиться к своим единоверцам в Северной Африке. Расстояние между Танжером и Тунисом составляет примерно 1200 миль, и прибрежная полоса, по большей части плодородная и изобилующая пресной водой, изрезана бесчисленным множеством укрытых от штормов естественных гаваней, идеально подходивших для их целей. Так родилась легенда о побережье Берберии.
Два знаменитейших на всем побережье пирата — Арудж и Хизр (более известный как Хайраддин) Барбароссы — были братьями. Родившиеся на острове Митилин (современный Лесбос), они были сыновьями отставного янычара, грека по рождению, ставшего горшечником, и его жены, овдовевшей после брака с греческим священником. (Так как все янычары изначально, до насильственного обращения в ислам, были христианами, в жилах братьев Барбаросса не текло ни капли турецкой, арабской или берберийской крови, дополнительным свидетельством чего служили их знаменитые рыжие бороды). В ранней юности Али — старший из двух — принимал участие в неудачной экспедиции против рыцарей ордена Святого Иоанна, во время которой те взяли его в плен и заставили служить на галерах. Его выкупили (кто — неизвестно). Вскоре после этого константинопольские купцы доверили ему капер; он служил под командованием мамлюкского правителя Египта.
В самом начале века братья появляются в Тунисе с двумя галиотами — большей частью открытыми судами, имевшими примерно по семнадцать весел, причем с каждым управлялись двое-трое гребцов. В 1504 г. в проливе, отделяющем остров Эльбу от материковой Италии, Арудж захватил первые важные трофеи: две папские галеры, загруженные до самого планшира дорогим товаром из Генуи. Они направлялись в Чивитавеккью, но так и не достигли места назначения: пираты взяли их на абордаж, захватили и с торжеством отвели в Тунис.
На следующий год также было совершено нападение на несколько испанских кораблей, причем с похожими результатами, и наконец в 1509 г. кардинал Хименес отрядил прославленного дона Педро Наварро, под командованием которого находилось не менее 90 судов и армия в 11 000 человек, якобы для распространения христианства вдоль североафриканского побережья, но на деле для того, чтобы призвать негодяев к ответу. Взятие Орана стоило испанцам всего 30 жизней; вслед за тем они хладнокровно перебили 4000 его жителей и вывезли в Испанию еще 5000 вместе с военной добычей, оценивавшейся в 500 000 золотых дукатов. На следующий год Бужи и Триполи постигла та же участь. Но сила Аруджа, к тому времени захватившего остров Джерба и устроившего там опорный пункт, откуда он совершал свои нападения, продолжала расти. В 1512 г. он откликнулся на просьбу изгнанного доном Педро правителя Бужи восстановить его власть в обмен на право свободно пользоваться портом. После мощного обстрела, продолжавшегося неделю, испанский гарнизон был готов сдаться, но тут удачным выстрелом Аруджу оторвало левую руку; он снял осаду, и флот возвратился в Тунис (правда, по дороге пираты захватили генуэзский галеон).
Генуэзцы не медлили в делах мести; их адмирал Андреа Дорна поспешил с двенадцатью галерами в Тунис, разграбил крепость и захватил половину пиратского флота. Но Арудж вновь перешел в наступление. В 1516 г. к нему поступила новая просьба — на этот раз от принца Селима из Алжира. Дон Педро не завоевал этот город, но два года назад, пытаясь воспрепятствовать постоянным нападениям алжирцев на корабли испанцев, последние выстроили укрепления на прибрежном острове в заливе, известном под названием Пеньон, откуда они полностью контролировали гавань и угрожали движению в обоих направлениях. Арудж не стал медлить. При попытке захватить Бужи он потерпел неудачу, но Алжир представлял собой куда более крупную добычу. Кстати, здесь можно было создать превосходную столицу великого Берберийского королевства, о котором он давно мечтал.