Bij de verdeling van het Romeinse imperium, in 395 na J. - C., Rhodos en de andere eilanden van „Provincia Insularum“ worden verbonden aan het Byzantijnse imperium.
Met het eind van het Romeinse imperium, vestigt de sombere periode van de hoge Middeleeuwen zich duurzaam.
Rhodos zal Byzantijns zijn, vergeten van het Westen, en geleverd aan de raids van de Arabische plunderaars perses vervolgens: het eiland wordt geplunderd en door het Boekweit in 653 verwoest; zij verkopen de resten van de Kolos, die op koopvaardijschepen worden ingescheept. In 661, maakt ervan de kalief Moawiyah zich meester, vervolgens heroveren de Grieken het.
Men herontdekt het eiland aan de tijd van de Kruistochten: de vaten op weg voor de Heilige Aarde doen er tussenlanding. Zij profiteert ervan om zich onafhankelijk te verklaren, ontsnapt aan het juk van Venetië maar valt onder die van Genua.
Génois zich er vestigen, drijven Jean Cantacuzène (1249) terug, maar door Théodore Protosebastos verjaagd; Rhodos wordt opnieuw aan het Byzantijnse imperium verbonden.