Пока изгнанный с Родоса орден пытался найти себе пристанище и залечивал раны в папской резиденции Витербо (папой Климентом Седьмым (1478–1534 гг., на кафедре с 19 ноября 1523 г.) к тому времени стал бывший иоаннит кардинал Джулио ди Медичи, верный, но малосильный друг ордена), оставшиеся на острове греки на себе почувствовали вероломство новых хозяев. Им же, как помнится, обещали освобождение от податей на 5 лет, свободное отправление богослужений – а вместо этого их всех выселили за пределы старого города, а все христианские храмы внутри городских стен были разорены и обращены в мечети. Что характерно, евреи остались жить в своем квартале. Часть греков подверглись насилию со стороны турок – впрочем, мародеры были наказаны султаном. Год спустя большая часть местных греков вымерла от бубонной чумы.
Оставшиеся решили действовать. В 1525 г. был организован заговор, во главе которого стал греческий священник Георгий. Он привлек на свою сторону даже большую часть из 300 янычар, охранявших крепость и форт Св. Николая! В письме Великому магистру Филиппу он сообщил о своих приготовлениях и просил прислать к острову три галеры и еще 6 судов, чтобы в назначенный день, а точнее в пятницу, когда турки будут на молитве, они по соответствующему сигналу (на башне Св. Николая и при входе в гавань поднимут крест) высадили десант, а янычары открыли бы им ворота. При этом Георгий выхлопотал у Филиппа персональную пожизненную пенсию для всех участников заговора, подтверждение прежних привилегий городу с добавлением новых, а также ограничение вмешательства латинского архиепископа в греческие церковные дела. Но заговор был провален.
В 1529 г. рыцари еще раз попытались вернуть остров при поддержке местного населения и опять же султанской оппозиции. Правитель Египта Ахмет-паша – тот самый, что осаждал Родос в 1522 г. – связался с римским папой и иоаннитами, обещая в случае удачи своего заговора вернуть им Родос. Правитель последнего, ага Ибрагим, был на стороне Ахмета. Рыцарский разведчик Антонио Босио прибыл на Родос, где встретился с митрополитом Евфимием, агой и греческими руководителями будущего восстания; в то же самое время Великий магистр заручился поддержкой императора Карла Пятого и короля Англии Генриха Восьмого (1491–1547 гг., правил с 1509 г.). Тем временем Ахмет-паша был убит, а заговор раскрыт – верховные турецкие власти немедленно заменили родосский гарнизон (видимо, его опять, как в 1525 г., хотя бы частично, да подкупили), арестовали и казнили агу, митрополита и все руководство восстания – как греческое, так и турецкое.
В следующем году мытарства бездомного ордена кое-как закончились (кстати, всем скитавшимся с ним грекам крестоносцы выделяли на прожитие полдуката в месяц); его новым домом стала Мальта, выделенная Карлом Пятым вместе со своеобразным «довеском» – крепостью в Триполи, в Северной Африке. Как не похож был этот пустынный, выжженный солнцем, практически безводный остров на утраченный райский Родос! Как убого выглядела старая крепостица Св. Ангела по сравнению с самой современной крепостью тогдашнего времени, чью восковую модель незадолго до осады 1522 г. вручили римскому папе! Местное население, которое власти, как всегда, «позабыли» спросить при выносе очередного исторического решения, встретило иоаннитов враждебно – в то время как истерзанные турками родосские греки так желали бы их возвращения! Но альтернативы не было.
Рыцари начали отстраивать старые укрепления и возводить новые. Их противниками по-прежнему оставались турки, а теперь к ним, благодаря географическому положению Мальты, прибавились еще и знаменитые алжирские пираты во главе с Хайреддином Барбароссой. Борьба велась с переменным успехом – в союзе с императором Карлом рыцари взяли арсеналы Барбароссы в Гулетте, где иоаннитами были освобождены 10 000 христиан и захвачены 300 вражеских медных пушек, а железных – бессчетно, и много кораблей (причем многие припасы и оружие, захваченные у алжирцев, были мечены королевской французской лилией – их снабжал король христианской Франции против своих единоверцев); с большим кровопролитием был разорен город Тунис, однако после героической обороны рыцари лишились своего аванпоста в Северной Африке – крепости Триполи, обороняемой маршалом ордена Гаспаром де Валье. Периодически на мальтийский архипелаг высаживались турки, производя опустошения и увозя людей в рабство. Рыцари не оставались в долгу, и постепенно ситуация начала все более и более накаляться. Новоизбранный в 1557 г. Великий магистр Жан Паризо де ла Валетт прозорливо начал готовить Мальту к перенесению большой осады. Престарелый султан Сулейман начал раскаиваться в своем юношеском благородстве, жалея, что «не додавил» иоаннитов, когда была возможность.