Хеир-Эддин с горстью верных турков отступил к Мегедии. Арабы равнины долго тревожили его и едва не захватили в плен, одно необыкновенное присутствие духа спасло его. Обманув преследователей, он переменил направление, перешел реку Баграду и отступил по направлению к Боне, но при переходе через Уэд-Меджерду он лишился Какчи-Диаболо, одного из лучших своих полководцев. Вскоре разнеслась весть, что этот отважный корсар, перенеся остатки своих богатств и отряд свой на десять галер, снова вышел в море. Адмирал Дориа отрядил вслед за ним эскадру, состоявшую из 14 кораблей под начальством одного генуэзского капитана, который, догнав страшного противника своего, не дерзнул вступить с ним в бой и поворотил назад в Тунис. Карл V, рассерженный такой трусостью, отправил немедленно самого Дориа с тринадцатью галерами и 2000 испанцев. Прибыв на место, адмирал нашел Бону оставленную жителями, которые скрылись в горах. Хеир-Эддин направил путь свой к Алжиру.
1 числа следующего августа Карл V заключил союз с Мулей-Гассаном, которого восстановил на тунисском троне, 17 того же месяца уехал по направлению к Сицилии и 22 прибыл в Трапани. Часть флота его взяла Бизерту и высадила гарнизон в Боне, но тот скоро покинул этот город, которым снова овладели турки.
Около исхода сентября, Хеир-Эддин выступил снова в море и явился перед Магоном. Корабли его, на которых были выставлены испанские флаги, обманули островитян, испуганный губернатор выдал город за личную свободу, все жители были увезены в неволю в Алжир.
При наступлении зимы Хеир-Эддин отправился в Константинополь и сильно помогал воинственной политике Сулеймана, который опять поручил ему начальство над флотом.
В 1541 году Карл V приготовился к новой экспедиции против Алжира. Он собрал 25тысячную армию, в которой считалось 500 мальтийских рыцарей. Флот его состоял из 360 судов разной величины.
Флот этот выступил из Майорки 18 октября, 20 очутился в виду Алжира и бросил якорь в двух милях от города. Первым делом Карла V было послать парламентера к губернатору Гассану-Аге с требованием сдачи города. Но незадолго перед тем, один марабут распустил слух, что страшная буря весьма скоро уничтожит близ Алжира какой-то сильный христианский флот. Гассан-Ага воспользовался этим предсказанием для ободрения турков, а между тем приготовил все для сильной обороны и отослал парламентера обратно, осыпав его насмешками. Лучшие и храбрейшие милиционные солдаты заняли ворота Баб-Азун, Баб-эль-Уэд, Морские и касбу (цитадель).
23 октября флот подошел на восток от города к устью Гарача, где ровный песчаный берег представляет удобное место для высадки. Войско поспешно сошло на берег, не встречая никакого препятствия, его разделили на три корпуса в 7000 человек каждый, и подошли на милю от ворот Баб-Азун. Армия была закрыта провалом, через который вел мост, она растянулась от берегов до высоты. Арабы издали перестреливались с ней, по своему обыкновению, но не смели вступить в серьезное сражение. Два испанских полка вытеснили их из домов, служивших ретраншаментами, и расположились на вершине самой высокой из гор, господствующих над Алжиром. Тогда только турки сознали важность этого пункта, на котором построили, после отплытия Карла V, крепость, вмещавшую до 1000 человек.
Рекогносцировка укреплений Алжира, не представлявших артиллерии сильного сопротивления, внушила Карлу V величайшую уверенность. Убежденный в быстром успехе, если поставит осажденных между огнем армии и флота, он приказал свезти на берег осадную артиллерию.
Но в девять часов вечера северо-восточный ветер, сопровождаемый проливным дождем, начал подымать на рейде волнение. Среди ночи ветер превратился в ураган и солдаты, палатки которых не были еще выгкружены, провели страшную ночь. На рассвете алжирцы сделали вылазку и сначала перебили много народа, отраженные потом, они отступили к городу и едва успели запереть за собой ворота, теснимые до того, что один мальтийский рыцарь успел воткнуть кинжал свой в Баб-Азунские ворота. Гассан-Ага, не теряя бодрости, приказал немедленно готовиться к новой вылазке, которая была гибельная для христиан. Кроме превосходства в числе, алжирцы имели и то важное преимущество, что подробно знали местность. Наконец, Карл V сам обнажил шпагу, собрал рассеянных солдат и повел их против неприятеля, который отступил, в свою очередь, и скрылся.
Между тем, буря, вместо того чтобы ослабевать, с часу на час становилась яростнее, корабли, бросаемые одни на другие, сваливались и разлетались в щепы. В короткое время было потоплено и разбито о скалы сорок из них. Весь берег от Алжира до Шершелля был покрыт мачтами, обломками, трупами; арабы, спустившиеся с гор, дорезывали утопающих.