Rhodos, am Schnittpunkt zwischen Ost und West gelegen, machte sich rasch die neuen Ideen des Christentums zu eigen. Nach der Überlieferung soll der Apostel Paulus im Jahre 58 n. Chr. den neuen Glauben in Lindos gelehrt haben und er soll in der Folge viele Bewohner der Insel zum Christentum bekehrt haben. Schon seit dem ersten Jahrhundert der christlichen Zeitrechnung hatte Rhodos einen Metropoliten mit Namen Prochoros. Später waren es Fotinos und Eufranor. Letzterer nahm am ersten ökumenischen Konzil in Nikäa teil.

Nach der Teilung des römischen Reiches wurde Rhodos zum Mittelpunkt der die Inseln umfassenden Provinz, doch erlangte es nie mehr den Ruhm und den Reichtum früherer Zeiten.

Rhodos, eingebunden in die wechselnden Schicksale des byzantinischen Reiches, erlebte fortan mehrfach Eroberungen und Zerstörungen. So eroberten 620 n. Chr. die Perser unter ihrem König Chosroe Rhodos. 651 n. Chr. fielen die Sarazenen über Rhodos her und 807 n. Chr. überfielen die Seldschuken unter Harun al Raschid die Insel und plünderten viele Kostbarkeiten.

Weitere Plünderungen der Insel ereigneten sich in der Regierungszeit des byzantinischen Kaisers Alexios I. durch Piraten.

Mit Beginn des elften Jahrhunderts begann Rhodos engere Beziehungen zum Westen zu knüpfen.

Mit Erlaubnis des byzantinischen Kaisers, gründeten die Venezianer im Jahre 1082 eine Handelsniederlassung im Hafen von Rhodos. Der sagenumwobene Engländer und spätere Kreuzritter Richard Löwenherz und Philipp von Frankreich kamen 1191 mit ihrer Flotte nach Rhodos und stellten dort die Truppen für ihren Kreuzzug zusammen.

Als die Kreuzritter 1204 Konstantinopel eroberten, machte sich der reiche Großgrundbesitzer Leon Gavalas dieses Ereignis zu Nutze und erklärte sich mit Unterstützung der Venezianer zum Herrn über Rhodos.

Nach der Rückeroberung Konstantinopels durch die byzantinischen Kaiser im Jahre 1261, gehörte Rhodos nominell zwar zum byzantinischen Reich, doch die Macht lag in Wirklichkeit bereits in den Händen der genuesischen Seefahrer, die die Insel regierten. Im Jahre 1306 verkaufte der Genuese Vignolo Vignoli Rhodos zusammen mit Kos und Leros an die Ordensritter des hl. Johannes von Jerusalem. Trotz heftigem Widerstand der Bevölkerung nahmen die Ordensritter 1309 die Insel in Besitz.