После того как Акра пала и существованию франкского Отремера пришел конец, рыцари-госпитальеры сначала нашли приют в Лимасоле. Однако они не желали подчиняться дому Лузиньянов, и в 1306 г. их магистр Фульке де Вилларэ — с благосклонного разрешения папы Климента — вступил в соглашение с генуэзским пиратом по имени Виньоло де Виньоли, дабы предпринять совместную атаку на остров Родос, принадлежавший тогда Византийской империи. В географическом отношении выбор был идеален. Из всех островов Эгейского моря Родос расположен дальше всего к востоку и всего в десяти милях от побережья Малой Азии; по проливу между ними проходила большая честь торговых кораблей, курсировавших между портами Западной Европы и Леванта. Горный хребет, достигающий примерно 4000 футов в высоту, давал несколько позиций, с которых можно было наблюдать как за Малой Азией, так и за островами Додеканес; в ясную погоду были видны даже очертания горы Иды на Крите, отстоящем более чем на сто миль к югу. Долины были покрыты садами и виноградниками, что решало вопрос с пищей и вином. Обширные сосновые леса обеспечивали обитателей Родоса практически неограниченными запасами древесины для строительства кораблей. Более того, жители острова могли похвастаться традициями мореплавания, восходившими ко временам античности. Экипаж судов римского флота на востоке (а впоследствии и византийских судов) состоял по большей части из родосцев. Если членам ордена, до сей поры базировавшимся на суше, теперь было суждено стать моряками, они не могли и надеяться найти себе лучших учителей в деле кораблестроения, в искусстве мореплавания и навигации.
Сначала, однако, нужно было завоевать остров. Его жители оказали упорное сопротивление, и только через два года тяжелой борьбы столица Родоса, близ которой находились две великолепные гавани, наконец оказалась в руках рыцарей. 15 августа 1309 г. ее ворота открылись, а через год она стала официальной штаб-квартирой ордена. С пиратом Виньоло госпитальеры быстро достигли соглашения, по которому рыцари в обмен на треть доходов с острова получали всю его территорию, кроме двух маленьких деревень, а также близлежащие острова Кос и Калимнос и некоторые другие из числа Додеканесских островов. Это была для них очень выгодная сделка. По прошествии девятнадцати лет они вновь обрели постоянный приют, дом на острове, который, согласно изданному впоследствии постановлению папы, полностью перешел в их собственность. С учетом этих новых обстоятельств они, являясь рыцарским орденом, образовали суверенное государство. Наконец-то они могли возобновить постоянную войну с неверными в соответствии со своим обетом «заставить замолчать врагов Господа». Но даже за этим занятием они никогда не забывали о том, что у них есть и другая обязанность, еще более неотложная. Эта их первая задача, после того как они поселились на Родосе, заключалась в том, чтобы начать работу в своем новом госпитале. Он должен был стать лучшим и самым известным во всем мире. Огромная больница — сохранившаяся до наших дней в том виде, в каком орден оставил ее почти пятьсот лет назад, — могла принять не менее восьмидесяти пяти пациентов, причем за всеми ухаживали сами рыцари.
Госпитальеры также создали совершенно новую административную структуру. Главой ее был гроссмейстер; орден, находившийся под его началом, подразделялся на восемь «лангов», то есть «языков», а именно Франции, Прованса, Оверни, Англии, Италии, Германии, Арагона и Кастилии. Чтобы объединить эту пеструю смесь рас и наречий, было решено, что каждый язык должен взять на себя ответственность за выполнение собственной задачи. Так, великий адмирал почти всегда был итальянцем, великий командор — провансальцем, великий маршал — овернцем, а великий бальи — немцем. Из числа англичан назначался туркополиер, отвечавший за береговые укрепления острова. От всех без исключения рыцарей требовалось, чтобы они носили на своем одеянии или плаще характерный восьмиконечный крест, «дабы в ум каждому запало, что он должен вечно хранить в сердце своем воспоминание о кресте Иисуса Христа и быть украшен восемью сопутствующими ему добродетелями».
В рамках «языков» орден подразделялся на три основных класса. Первый состоял из «рыцарей справедливости», набиравшихся только из аристократических фамилий Европы; от них требовали надежных доказательств их знатного происхождения. Следующими с точки зрения иерархии шли орденские служащие братья, чей социальный статус был несколько ниже; одни были воинами, другие — дипломатами, прочие должны были работать в госпитале. Третья категория состояла из капелланов, служивших в храмах и часовнях. Каждый рыцарь должен был в течение первых двух лет выдерживать испытательный срок службы, причем один из них он проводил на галерах. Лишь после этого с него брали следующую клятву: