Хеир-Эддин с горстью верных турков отступил к Мегедии. Арабы равнины долго тревожили его и едва не захватили в плен, одно необыкновенное присутствие духа спасло его. Обманув преследователей, он переменил направление, перешел реку Баграду и отступил по направлению к Боне, но при переходе через Уэд-Меджерду он лишился Какчи-Диаболо, одного из лучших своих полководцев. Вскоре разнеслась весть, что этот отважный корсар, перенеся остатки своих богатств и отряд свой на десять галер, снова вышел в море. Адмирал Дориа отрядил вслед за ним эскадру, состоявшую из 14 кораблей под начальством одного генуэзского капитана, который, догнав страшного противника своего, не дерзнул вступить с ним в бой и поворотил назад в Тунис. Карл V, рассерженный такой трусостью, отправил немедленно самого Дориа с тринадцатью галерами и 2000 испанцев. Прибыв на место, адмирал нашел Бону оставленную жителями, которые скрылись в горах. Хеир-Эддин направил путь свой к Алжиру.

1 числа следующего августа Карл V заключил союз с Мулей-Гассаном, которого восстановил на тунисском троне, 17 того же месяца уехал по направлению к Сицилии и 22 прибыл в Трапани. Часть флота его взяла Бизерту и высадила гарнизон в Боне, но тот скоро покинул этот город, которым снова овладели турки.

Около исхода сентября, Хеир-Эддин выступил снова в море и явился перед Магоном. Корабли его, на которых были выставлены испанские флаги, обманули островитян, испуганный губернатор выдал город за личную свободу, все жители были увезены в неволю в Алжир.

При наступлении зимы Хеир-Эддин отправился в Константинополь и сильно помогал воинственной политике Сулеймана, который опять поручил ему начальство над флотом.

В 1541 году Карл V приготовился к новой экспедиции против Алжира. Он собрал 25‑тысячную армию, в которой считалось 500 мальтийских рыцарей. Флот его состоял из 360 судов разной величины.

Флот этот выступил из Майорки 18 октября, 20 очутился в виду Алжира и бросил якорь в двух милях от города. Первым делом Карла V было послать парламентера к губернатору Гассану-Аге с требованием сдачи города. Но незадолго перед тем, один марабут распустил слух, что страшная буря весьма скоро уничтожит близ Алжира какой-то сильный христианский флот. Гассан-Ага воспользовался этим предсказанием для ободрения турков, а между тем приготовил все для сильной обороны и отослал парламентера обратно, осыпав его насмешками. Лучшие и храбрейшие милиционные солдаты заняли ворота Баб-Азун, Баб-эль-Уэд, Морские и касбу (цитадель).

23 октября флот подошел на восток от города к устью Гарача, где ровный песчаный берег представляет удобное место для высадки. Войско поспешно сошло на берег, не встречая никакого препятствия, его разделили на три корпуса в 7000 человек каждый, и подошли на милю от ворот Баб-Азун. Армия была закрыта провалом, через который вел мост, она растянулась от берегов до высоты. Арабы издали перестреливались с ней, по своему обыкновению, но не смели вступить в серьезное сражение. Два испанских полка вытеснили их из домов, служивших ретраншаментами, и расположились на вершине самой высокой из гор, господствующих над Алжиром. Тогда только турки сознали важность этого пункта, на котором построили, после отплытия Карла V, крепость, вмещавшую до 1000 человек.

Рекогносцировка укреплений Алжира, не представлявших артиллерии сильного сопротивления, внушила Карлу V величайшую уверенность. Убежденный в быстром успехе, если поставит осажденных между огнем армии и флота, он приказал свезти на берег осадную артиллерию.

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

Между тем, буря, вместо того чтобы ослабевать, с часу на час становилась яростнее, корабли, бросаемые одни на другие, сваливались и разлетались в щепы. В короткое время было потоплено и разбито о скалы сорок из них. Весь берег от Алжира до Шершелля был покрыт мачтами, обломками, трупами; арабы, спустившиеся с гор, дорезывали утопающих.

26‑го император, видя, что половина флота и припасы всех родов уничтожены, приказал войску отступить до мыса Матифу. Раненых поместили в середине и отступление совершилось в должном порядке до берегов Гарана, среди несметных туч арабов. Реку, воды которой поднялись от дождей, невозможно было пройти вброд, оставалось остановиться на берегу ее. Карл V, расположив лагерь треугольником, одна только сторона которого обращалась к неприятелю, а две другие опирались на море и на реку, приказал собрать обломки, выброшенные на берег, и построить мост, но на другой день вода упала и армия перешла реку вброд. Турки прекратили преследование, оставалось отбиваться от арабов. На следующий день пришли к Гамису, глубокой тинистой реке, через которую надо было построить мост. Наконец, 30 октября армия достигла мыса Матифу и расположилась в римских развалинах Рузгуниума. 1 ноября Карл V приказал посадить на суда свое войско, упавшее духом, но едва половина была перевезена на них, как поднялась новая буря страшнее первой. Корабли поспешили выбраться в открытое море и, наконец, кое-как, поодиночке, достигли в различных местах берегов Италии, где весть об этом бедствии распространила горесть и смущение.

Карл V оставил Африку 3 ноября, 4 поехал в Бужию, где пробыл две недели в ожидании, чтобы волнение улеглось, выехал из нее 17 и принужден был возвратиться в нее по причине новой бури. Наконец, 23 числа снова вышел в море и достиг Майорки, откуда 1 декабря уехал в Картахену.

Таков был конец этой плачевной экспедиции, память о которой навсегда останется в истории. О ней говорится почти то же самое в арабских летописях, разумеется, с некоторыми вариациями в пользу мусульман.

Неудача Карла V усилила еще более дерзость алжирских пиратов, которые прозвали город свой «непобедимым». Они снова принялись за свои опустошительные набеги. Марабут, предсказавший гибель христианского флота, был почитаем как святой. Память его чтут в Алжире доныне.

Узнав о поражении своего соперника, Франциск I стал надеяться на довершение его гибели, если воспользуется расстройством императора и потому немедленно вступил в еще теснейшие связи с Сулейманом. Султан прислал ему флот в 150 судов, который отплыл 28 мая 1543 года под начальством Хеир-Эддина, 20 июня разрушил и сжег Реджио, мимоходом погрозил Риму и 5 июля бросил якорь перед Марселью. Но вскоре пират, заметив, что ничего не готово для какой бы то ни было экспедиции, наскучил бездействием и громко изъявил свое неудовольствие. Король, казалось, колебался и не смел уже воспользоваться флотом, которого просил так убедительно. Он боялся восстановить против себя всю Европу, приняв под знамена Франции исступленных мусульман, не обращавших никакого внимания на права народные. Наконец, он дал нерешительное приказание атаковать Ниццу. Французские и турецкие войска действовали согласно и сначала успешно, но известие, что дю-Гваст и Дориа приближаются с моря и с суши на выручку со значительными силами, распространило между осаждающими такой ужас, что они отказались от своего предприятия. Хеир-Эддин возвратился в Тулон, откуда отправил 25 галер грабить города Испании, маленькая эскадра эта отвезла свою добычу в Алжир, где перезимовала. Хеир-Эддин пробыл до следующего лета в Тулоне, занятый починкой своих судов и таинственными переговорами с Дорией. Генуя, казалось, искала дружбы со старым пиратом, завязались переговоры о размене пленных, причем особенно восхищал Хеир-Эддина размен знаменитого Драгута, который тотчас получил начальство над галиотом. Драгут впоследствии сделался одним из самых смелых разбойников на Средиземном море.