Сулейман. Султан Востока   ::   Лэмб Гарольд

Имя Барбароссы стало обрастать легендами и в Европе. Его искали и не могли найти, а он появлялся повсюду. Испанские галеры перехватили Барбароссу, когда он перевозил изгнанных мавров, не имевших возможности переселиться самостоятельно, из Андалузии в Африку. Барабаросса прибавил эти галеры к своему небольшому флоту из тридцати пяти галиотов. Также он завладел папскими галерами, а их экипажи сделал гребцами.

Когда Карл V в качестве короля Испании приказал очистить страну от оставшихся мавров (после того как его освободили от клятвы во время коронации воздерживаться от насильственного обращения людей в чужую веру), Барбаросса совершил набег на испанское побережье. Нападая на церкви и гарнизоны внутри страны, он использовал в качестве проводников местных мусульман. А уходя с добычей, увез их как пассажиров. В целом Барбаросса вывез семьдесят тысяч мавров, ненавидевших испанцев так же сильно, как и он сам, а затем составивших основу его корабельных команд.

Карла раздражало присутствие в Западном Средиземноморье морских разбойников. Вместе с Барбароссой действовали Синан, еврей из Смирны, способный определять высоту солнца над горизонтом при помощи приклада арбалета, Какка диабола (Бей дьявола) и Салих Раис, тучный араб с Нила, который управлял его баркой. Но выкурить их оттуда было трудно. Вытесненные из Беджами, они появлялись в Алжире. Испанцы владели островом Пеньон-де-Алжир, сторожившим вход в небольшую бухту.