Впоследствии критики ордена, размышляя о его упадке в XVII и XVIII веках, посчитали, что рыцари были не лучше, чем мусульманские корсары. Истина совсем не такова. Орден святого Иоанна, в то время как его рыцари действительно нападали на мусульманское судоходство, в основном заботился о стабилизации торговых путей Центрального Средиземноморья и установлении хотя бы какого-нибудь порядка на море, где никто не помышлял о законе.
Исполнившись решимости избавиться от мусульманской угрозы своему королевству, Карл V наконец сумел вытеснить Барбароссу и его людей из Туниса. Вдохновленный успехом, он сделал попытку захватить город Алжир, расположенный даже ближе к Испании и являвший собой еще большую угрозу испанским коммуникациям и ее владениям в Новом Свете. Дополнительной причиной желания Карла очистить от корсаров Алжир было то, что теперь, когда Тунис был у него в руках, было легко представить в руках христиан и североафриканское побережье со всеми главными гаванями от Алжира до Триполи. А ситуация в Триполи была тяжелой, о чем великий магистр Омедес не уставал напоминать. Построенный на подвижном песке, окруженный враждебными племенами город требовал постоянных расходов, которые орден не мог себе позволить, когда все средства тратились на обеспечение безопасности Мальты. На очередной запрос Карлу V выделить дополнительные средства на укрепление города или позволить рыцарям покинуть его монарх ответил, что готовит экспедицию на Алжир, и если рыцари помогут ему уничтожить корни всех неприятностей, то, он уверен, Триполи можно удержать.
Экспедиция, начавшаяся в 1519 году – это был первый год правления Барбароссы в Алжире, – была впечатляющим примером европейского сотрудничества. Была собрана международная армада. За исключением Франции, страны, у которой были «напряженные отношения со всеми своими христианскими соседями», почти все государства, имевшие интересы в Средиземном море, внесли вклад в ее формирование. Атаку должны были возглавить 50 боевых галер, а для перевозки армии было приготовлено от 300 до 400 судов. Папа выделил эскадру галер. То же самое сделали Неаполь, Монако и Испания. Фернандо де Гонзага и Андреа Дориа привели 20 кораблей. Орден отправил 500 рыцарей, у каждого по два помощника. Это был corps d’elite для формирования авангарда в нападении на город. К сожалению, как это часто бывало в те дни, когда проблемам обеспечения не уделяли должного внимания, армада вышла в море намного позже, чем планировалось, и только 24 августа флот бросил якоря в Алжирском заливе.