Lors de la division de l’empire romain, en 395 après JC, Rhodes et les autres îles de la « Provincia Insularum » deviennent rattachées à l’empire byzantin.
Avec la fin de l’empire romain, la période sombre du haut Moyen Âge s’installe durablement.
Rhodes sera byzantine, oubliée de l’occident, et livrée aux raids des pillards perses puis arabes : l’île est pillée et dévastée par les Sarrasins en 653 ; ils vendent les restes du Colosse, qui sont embarqués sur des navires marchands. En 661, le calife Moawiyah s’en empare, puis les Grecs la reconquièrent.
On redécouvre l’île au temps des Croisades : les vaisseaux en route pour la Terre Sainte y font escale. Elle en profite pour se déclarer indépendante, échappe au joug de Venise mais tombe sous celui de Gênes.
Les génois s’y établissent, repoussent Jean Cantacuzène (1249), mais sont chassés par Théodore Protosebastos ; Rhodes est de nouveau rattachée à l’empire byzantin.