Bei der Division des römischen Imperiums in 395 nach J. - C., Rhodos und die anderen Inseln „Provincia Insularum“ werden mit dem byzantinischen verbunden Imperium.
Mit dem Ende des römischen Imperiums installiert sich die dunkle Periode des hohen Mittelalters dauerhaft.
Rhodos, wird vergessen vom Okzident und den überfällen der arabischen Plünderer Perser geliefert dann byzantinisch sein: die Insel wird geplündert und wird durch den Buchweizen in 653 verwüstet; sie verkaufen die Reste des Kolosses, die auf Handelsschiffen eingeschifft werden. In 661 bemächtigt sich der Kalif Moawiyah davon, dann erobern die Griechen zurück es.
Man entdeckt die Insel an der Zeit der Kreuzzug wieder: die Schiffe unterwegs für die heilige Erde machen dort Aufenthalt. Sie davon profitiert, um sich unabhängig zu erklären, entgeht dem Joch von Venedig, aber fällt unter jenes von Genua.
Die génois stellen sich dort auf, drängen Jean Cantacuzène (1249) zurück, aber werden von Theodor Protosebastos verjagt; Rhodos ist erneut mit dem byzantinischen Imperium verbunden.