Теперь Аруг, располагая базой и флотом, начал планомерные набеги на острова Средиземного моря и Испанию. Даже самые сильные "адмиралтейства" не были в безопасности. Никакой замок не мог полагаться на свои укрепления, села и города в прибрежной зоне начали пустеть. Под кирпичными сводами тунисского базара возник один из самых больших в истории Невольничьих рынков.
Только знатным дворянам да богатым купцам удавалось освободиться за выкуп. Простым пленникам предстояло до конца дней нести бремя тяжелых работ или грести на галерах. Аруг воскресил средиземноморскую работорговлю в масштабах, которых она не достигала со времени Древнего Рима.
Позже, перессорившись с тунисским султаном из-за добычи, Аруг перенес свою "штаб-квартиру" на один из скалистых средиземноморских островов, попутно прихватив тунисские корабли. Мулей Ахмету оставалось лишь проклинать обманщика.
Теперь на Средиземном море не было человека, который не слышал бы об Аруге. "Красная борода",- говорили, испуганно крестясь, бывалые шкиперы, увидев паруса на горизонте.
И вот настал день, когда корабли Аруга поднялись по Тибру к священным стенам Рима.
Напуганный папа Юлий II отдал приказ начать войну с пиратом. Две окрашенные в красный цвет галеры, на парусах которых были нарисованы тиара и скрещенные ключи (герб римских пап), поджидали Аруга в устье Тибра. Спасения не было. Итальянский капитан Паоло Витторио перебил половину пиратского экипажа, а главаря шайки захватил в плен.
Связанный по рукам и ногам Аруг был брошен в вонючий трюм, куда доносились восторженные крики захмелевших итальянских солдат. На палубе шел пир и дележ добычи. Награбленное пиратами добро перекочевывало в сундуки папских наемников. В каютах спорили и смеялись. Песни сменялись драками.
Но счастье не покинуло Аруга. Кусочком дерева ему удалось перетереть веревки. Освободившись сам, он разрезал путы и на оставшихся в живых сообщниках. Когда итальянская команда перепилась, капитан Паоло Витторио был обезоружен и убит пиратами, а его матросы захвачены.
Оба папских корабля стали добычей Аруга.
На этот раз он не обратил пленных в рабство. Они были поодиночке высажены по всему побережью Италии и Испании для того, чтобы сеять панику. Молва должна была увеличить могущество Аруга во сто крат.
Услышав о победе пирата, тунисский султан решил пойти на мировую с вероломным союзником, и в 1514 году гавань Туниса снова стала базой пиратов. За это Аруг обязался отбить у испанцев крепость Бужию.
* * *
Усиление пиратства уже давно беспокоило Испанию. Но борьба с пиратами требовала денег, а казна была пуста. И тогда толедский кардинал Хименэс решил отдать доходы всех церквей в Толедо на поход в Северную Африку. Успех сопутствовал Хименэсу. В упорной борьбе испанцы захватили Оран и другие ключевые крепости Северной Африки. У самого входа в Алжирскую гавань в 1505 году был построен неприступный замок Пеньон, которому Хименэс придавал особое значение. А затем пришла очередь Бужии, Тлемсена и Алжира.