В апреле орден переехал в Мессину на Сицилии. Поскольку Крит принадлежал Венецианской республике, а венецианцы вели себя с турками осторожно, они не желали оказывать гостеприимство рыцарям слишком долго.

Но пребывание рыцарей в Мессине тоже было недолгим. Мессина принадлежала испанскому королю. Губернатор Сицилии, подданный короля, выступал против того, чтобы рыцари основали здесь свою крепость. Ордену пришлось переезжать с места на место вместе со своими святынями и боевыми знаменами: в Геную, Ниццу и Витербо в Центральной Италии. За это время Л’Илль-Адан даже навестил правящих монархов Европы, не уставая призывать к крестовому походу, чтобы вернуть Родос. Однако короли не испытывали особого восторга от его предложения.

В 1527 году, спустя пять лет после падения Родоса, произошло важное событие. Армия императора Священной Римской империи Карла, короля Испании, напала на Рим, где восседал папа, сожгла и разграбила город. Рим явно был не в состоянии думать о крестовом походе против турок. Рыцарям ордена пришлось признать, что нужно оставить любые надежды на возвращение на Родос. Они стали обращаться к монархам Западной Европы с просьбой о новом месте. Они просили Сицилию, часть Сардинии, затем часть Корсики; в качестве последнего прибежища они даже подумывали об острове Эльба. Но ни один из этих планов не был реализован.

В 1530 году Карл вспомнил, что в его владениях находилось три средиземноморских острова: Мальта и два других. Он подумал, что может отдать эти острова рыцарям; был подписан договор, согласно которому рыцари обязались каждый год выплачивать дань. Однако пока остров находился в руках ордена, рыцари считались подданными Испанского королевства. Им поручили напасть на Триполи в Северной Африке.

Из этого ясно видно, как Карл намеревался воспользоваться орденом. Он собирался править всей Северной Африкой, включая Алжир и Тунис, и хотел, чтобы рыцари защищали его торговые суда от мусульманских пиратов (известных под именем пиратов Барбароссы), которые наводили на всех ужас. Османской империи не хватало власти на море, и поэтому они наделили пиратов властью на суше и в портах Северной Африки при условии, что в случае необходимости они предоставят турецкому флоту свои корабли.

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

Великий магистр прекрасно это осознавал. Но если бы он отказался от Мальты, неизвестно, когда и где им удалось бы основать новую крепость. Причиной дальнейшего существования ордена могло быть просто избавление от пиратов, но все же это была причина. Чтобы сохранить орден, им было важно получить крепость и цель.

В 1530 году, восемь лет спустя после их изгнания с Родоса, орден закончил переселение на Мальту.

Однако условия, существовавшие на острове, повергли рыцарей, привыкших к древнему острову Цветущих роз, в состояние отчаяния.

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

После переезда несколько рыцарей из каждой «нации» покинули орден. В качестве оправдания они заявили, что на Мальте лишились смысла существования их ордена. Стать гончей Карла было ниже их рыцарского достоинства. Ла Валетт, который высказывал те же мысли на Родосе, настаивая на продолжении сопротивления, остался в ордене. Возможно, в его памяти отпечатался образ турецкого победителя, которому было столько же лет, сколько и ему.

Великий магистр Л’Илль-Адан умер на Мальте спустя четыре года после переезда. Примерно в это же время на острове стали происходить изменения.

Если на Родосе были строения, сохранившиеся с византийских времен, на Мальте приходилось строить все заново. Прибыв на Родос, они пользовались обнаруженными строениями, но со временем и ростом возможностей иоанниты стали расширять, перестраивать и переоборудовать эти строения, чтобы возвести самую прочную крепость в Средиземноморье. Совершить такой подвиг на Мальте, где не было ни одного древнего или средневекового строения, было невозможно. К тому же, с точки зрения рыцарей и согласно здравому смыслу тех времен, нельзя было представить себе жизнь без какой-либо крепости. Возможно, единственным достоинством голого Мальтийского острова было обилие бухт, глубоко вырезанных среди зазубренных скал. Если над ними достаточно потрудиться, то они могли бы превратиться в прекраснейшие порты Средиземноморья.

Рыцари стали укреплять этот участок земли, на котором никто не жил. Как и в былые времена, планировкой и надзором за выполнением работ занимались итальянские фортификаторы. Рыцари решили сделать это место, которое до сих пор оставалось безымянным, своей столицей. Когда умер Л’Илль-Адан, работа по возведению крепости была в самом разгаре, но Великие магистры, пришедшие после него, придерживались его взглядов и делали все возможное, чтобы достроить крепость. В 1557 году, спустя двадцать семь лет после переезда на Мальту, фортификационное сооружение на заливе было наполовину готово. Для этого понадобилось по очереди укрепить все восемь полуостровов, выходивших в залив. Теперь у ордена было меньше средств, чем раньше, поэтому строительство затянулось.