Не удовлетворившись этой блистательной победой, Барбаросса в 1534 году на шестидесяти галерах вновь форсировал Мессинский пролив, захватил портовый город Реджо в Калабрии и прошелся по всему западному побережью Италии вплоть до Генуи, заполнив пленниками палубы и трюмы всех своих кораблей. (Об этом его рейде потом слагали легенды, иногда весьма пикантного содержания, где в числе персонажей можно найти красавицу-вдову и ее молодого слугу, а сюжетное действие сопровождается бешеной ночной скачкой молодой княгини через лес и «кровавой оргией» разочарованных пиратов. Все это, скорее всего, именно легенды, хотя доля истины в них может быть.)
В следующем году он захватил город Тунис, чей бей Мулен Хасан, как доложили Барбароссе, был подкуплен Карлом V. Год спустя Андреа Дориа удалось отбить Тунис, но цена оказалась чрезмерно высокой: пока испанцы в поте лица трудились у стен тунисской столицы, эскадра пиратов совершила молниеносный рейд к Балеарским островам, разорила Менорку и захватила на ней шесть тысяч пленных. Хайр-эд-Дин почтительнейше преподнес их в дар турецкому султану.
Дориа, этот кондотьер, продававший свою шпагу тем, чей кошелек выглядел внушительней, официально числился адмиралом испанского флота, слыл национальным героем и пользовался всеми преимуществами полноправного гражданина. Барбароссу, даже в самые отчаянные моменты сохранявшего верность своему султану, везде преследовала слава вероотступника, разбойника и плебея. Преследовала на протяжении всех шестидесяти лет, когда он верой и правдой служил своему султану.
Чтобы восстановить справедливость, Сулейман 15 октября 1535 года пожаловал Хайр-эд-Дину фирман (указ), возводивший преданного слугу в достоинство капудан-паши (главнокомандующего османским флотом) и бейлербея (бея над беями, по европейским понятиям - вице-короля) Северной Африки.
Барбаросса не обманул доверия своего благодетеля. В феврале 1536 году он был направлен султаном к Франциску I, чтобы защитить Францию от притязаний Карла. Когда его корабли проходили Мессинским проливом, их неожиданно обстреляли пушки города Реджо-ди-Калабрия. Трудно сказать, на что рассчитывали городские власти: должно быть, у них просто сдали нервы. Расплата за это легкомыслие последовала незамедлительно: Барбаросса огнем судовых орудий подавил батареи Реджо, а высаженные на берег двенадцать тысяч янычаров предали город огню и мечу. После того как пиратские галеры прибыли в Марсель, где Барбароссу встретили как самого султана, Франциск довольно скоро пожалел о своей опрометчивой просьбе: пираты методично и без разбора грабили все подряд до самой Лигурии, И французам приходилось за умопомрачительные суммы выкупать кораблях у них своих же соотечественников. Никакие увещевания не действовали на железного Хайр-эд-Дина. Наконец Франциск I уведомил Сулеймана, что помощь больше не требуется, и флот Барбароссы отбыл восвояси вдоль побережья Италии, разграбив по пути все острова от Эльбы до Липары, какие оказывались на его пути. Чуть позже Барбаросса захватил Бизерту и несколько островов, принадлежавших Венеции.
Однако 1537 год оказался несчастливым для капудан-паши: в стычке с Дориа около Мессины он потерял двенадцать галер. Ярость Барбароссы слегка улеглась лишь после того, как молодцы с уцелевших его кораблей затопили кровью побережья Апулии и острова Корфу. Дориа между тем торжествовал победу, осыпаемый милостями Карла. Но радость была преждевременной. Год спустя, 25 сентября 1538 года в морском сражении у Ионических островов, в заливе Превеза, флот капудан-паши наголову разгромил испанско-венецианскую армаду, которой командовал Андреа Дориа, после чего Венеция, скрепя сердце, вынуждена была заключить позорный мир с Турцией. А еще через два года Хайр-эд-Дин закрепил свое превосходство на море, уничтожив другой христианский флот при Кандии, у северных берегов Крита.
Союз султана с Хайр-эд-Дином очень напоминает аналогичный союз понтийского царя Митридата с киликийцами. Как и те, варварийские разбойники всегда были уверены в поддержке и благосклонности султана. Султан, со своей стороны, отчетливо сознавая, что его подданных трудно назвать морской нацией, возлагал на пиратов все свои надежды на море и именно в алжирских молодцах видел своих учителей в области мореходства и судостроения.
Престиж Карла в Европе таял на глазах, необходимо было срочно спасать его. Единственное, что могло восстановить сильно пошатнувшийся авторитет императора,- это ликвидация пиратской столицы Средиземноморья - Алжира. На разработку плана его захвата ушло около трех лет.