En la división del imperio romano, en 395 después de J. - C., Rodas y las otras islas del “Provincia Insularum” se vuelven adjuntas al imperio bizantino.
Con el final del imperio romano, el período oscuro de la alta Edad Media se instala duraderamente.
Rodas será bizantina, olvidada del occidente, y suministrada a las incursiones de los ladrones persas luego árabes: la isla es pillada y devastada por los Alforfones en 653; venden los restos del Coloso, que se embarcan sobre buques comerciales. En 661, el califa Moawiyah se apodera, luego los Griegos lo reconquistan.
Se redescubre la isla al tiempo de las Cruzadas: las naves en marcha para la Tierra hay escala. Aprovecha para declararse independiente, escapa al yugo de Venecia pero cae bajo el de Génova.
Théodore Protosebastos expulsa los génois se establecen, rechazan a Jean Cantacuzène (1249), pero; Rodas de nuevo está vinculada al imperio bizantino.