Права на правление Алжиром он не имел ровным счетом никакого. Просто этот предприимчивый морской пират, воспользовавшись борьбой алжирцев против испанских колонизаторов, захватил власть в стране, но, чувствуя свою слабость, вынужден был обратиться за помощью к Турции, чьим вассалом и стал в 1519 году. Имея за спиной столь сильную поддержку, Хайреддин осмелел и стал совершать все более частые набеги на испанские владения в Северной Африке. Борьба против него становилась крайне необходимой еще и потому, что, нанося удары алжирскому правителю, Карл V одновременно весьма чувствительно задевал и Османскую империю, уже распространившую свою власть практически на все африканское побережье от Алжира до Египта и пытавшуюся прибрать к рукам Марокко.
В те времена немало европейских монархов относилось к Средиземному морю как к своей вотчине. Не отставали от них ни турки, ни алжирские пираты, наводившие страх на европейские страны бассейна. Они убивали и грабили прибрежное население, опустошая целые районы, увозили в плен тысячи рабов, захватывали суда и добычу, постоянно угрожая торговому мореплаванию. Вот против этой-то «заразы» и призвал глава Священной Римской империи выступить орден, ставший отныне Мальтийским.
Этот военно-морской выпад рыцарей против новоявленного алжирского правителя прошел успешно: по некоторым источникам, было освобождено 10 тыс. пленников-христиан. Однако через шесть лет Хайреддин взял убедительный реванш, разбив силы Карла V под г. Алжиром. В кампании вновь участвовали госпитальеры, понесшие ощутимые потери: испанский флот, в который влились их корабли, был разметен и практически уничтожен жестоким штормом. Рыцарям приходилось туго: в военных предприятиях их преследовали неудачи; еще хуже обстояло дело с финансами, и уж совсем плохо складывались дела внутри ордена. За десятилетие, прошедшее с момента воцарения ордена на Мальте, значительно обострились разногласия рядовых рыцарей с орденской верхушкой, вызванные чрезмерными амбициями великого магистра с его окружением и стремлением молодых членов братства освободиться от суровой дисциплины и мелочной опеки.
Время шло, а неудачи продолжались, как во внутренних делах, так и в международных. В 1540 году орден постигла двойная неудача, усугубившая его и без того сложное положение: он потерял свои владения и, следовательно, огромные доходы в Англии и Германии. Предлогом для конфискации владений послужили события Реформации: местные монархи и князья увидели прекрасную возможность укрепить свою власть и освободиться от диктата Рима.