Неудачи начали преследовать экспедицию с самого начала 28 сентября 1541 года испанский флот вышел в море и попал в жестокий шторм, обычный для этого времени года Ценой больших усилий испанские корабли смогли зайти в порт Маон на Балеарских островах. Значительная часть кораблей при этом получила серьёзные повреждения, но это не остановило испанского монарха.
В конечном итоге в бухте Пальма де Майорка собрался весь союзный флот. Около пяти сотен кораблей из Испании, Генуи, Неаполя, Сицилии, папского государства и Мальтийского ордена На них располагалась армия вторжения из 24 тысяч солдат.
Несмотря на шторм, 19 октября флот прибыл к Алжиру. Карл V впервые увидел пиратскую столицу собственными глазами — город, окружённый крепостной стеной, расположенный на скалистой возвышенности. В течение трёх дней из-за сильного прибоя войска не могли высадиться на берег. Наконец, 23 октября установилась хорошая погода и вторжение началось. Христианские войска расположились вокруг города. Правое крыло образовали силы Мальтийского ордена и итальянских государств, центр — немецкая армия герцога Альбы, левое крыло — испанцы. Отбив вялые атаки арабской кавалерии, войска двинулись к городским укреплениям Учитывая превосходство сил атакующих, ни у кого не возникло сомнений в исходе сражения. Им противостояли около восьми сотен турок и примерно пять тысяч арабов во главе с Хасаном, однако на предложение сдаться осаждённые ответили отказом.
Тогда испанцы начали классическую осаду. К городу были подтянуты артиллерийские орудия, которые должны были разрушить городские стены и открыть путь штурмовым колоннам В тот момент, когда надежда должна была покинуть алжирцев, им на помощь пришла природа. Старый адмирал Дориа не зря предупреждал об опасности осенних начинаний в Северной Африке. Внезапно начались затяжные дожди в сочетании с сильным ветром Ветер сбил все палатки в испанском лагере, и солдаты были вынуждены мокнуть под открытым небом Измученные, усталые и промокшие, они с удивлением увидели, что алжирцы сделали вылазку из города. Дождь потушил фитили и намочил порох, поэтому испанцы оказались в самой неприглядной ситуации. Паника охватила испанскую армию и её союзников. Только стойкость рыцарей Мальтийского ордена позволила отбить внезапную атаку врага и загнать его обратно в городскую цитадель. Мальтийцы попытались ворваться в город вслед за отступающими арабами, однако гарнизон вовремя закрыл городские ворота и открыл такой сильный огонь, что христианам пришлось спешно отступить в свои траншеи.
Тогда Хасан атаковал лагерь противника при помощи своих лучших всадников, ударив по флангу вражеской армии. Итальянцы не выдержали удара и обратились в бегство. Попытка укрепить фланг за счёт немецких наёмников также не увенчалась успехом Сам император был вынужден спешно облачиться в доспехи в ожидании нападения врага Только личное мужество Карла V привело в чувство отступающих солдат. Весь остаток дня испанские офицеры приводили в чувство своих подчинённых и под проливным дождём ожидали новых вылазок.
Несколько драгоценных дней христианская армия провела в работах по восстановлению и укреплению своего лагеря.
25 октября на испанцев обрушилась новая беда — свирепый северо-восточный шторм застал флот в самое неподходящее время. Якоря не могли удержать корабли на песчаном грунте, и они медленно приближались к берегу, грозящему им гибелью. Один за другим корабли выбрасывались на берег и разбивались прибоем В течение шести часов затонуло около 150 кораблей, ещё 15 были выброшены на берег и попали в качестве трофеев к алжирцам На утро адмирал Дориа осматривал то, что осталось от его флота Пророчество адмирала сбылось. Даже те корабли, что остались на плаву, получили слишком серьёзные повреждения и нуждались в ремонте.
Учитывая всю серьёзность положения, Дориа посоветовал императору немедленно свернуть экспедицию, поскольку на затонувших кораблях располагалась львиная доля запасов провизии и армии реально грозил голод. Всего за несколько дней гордая испанская армия превратилась в своё жалкое подобие. Солдаты уже несколько дней подряд не могли просушить свою одежду, разогреть горячую пищу также было невозможно. Кроме того, сильно похолодало, и это только увеличило муки солдат. Лагерь превратился в болото. Порох промок и не годился для стрельбы, а вокруг постоянно рыскали арабские отряды, отлавливавшие зазевавшихся солдат. Кроме того, выяснилось, что боевые качества итальянских и немецких солдат были, мягко говоря, недостаточными для ведения нормальной войны, а испанских частей было крайне мало для ведения осады.