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