In 395, the long Byzantine period began for Rhodes, when the eastern half of the Roman empire became gradually more Greek.
Beginning after 600 AD, its influence in maritime issues was manifested in the collection of maritime law known as "Rhodian Sea Law" (Nomos Rhodion Nautikos), accepted throughout the Mediterranean and in use throughout Byzantine times (and influencing the development of admiralty law up to the present).
Rhodes was occupied by the Islamic Umayyad forces of Muawiyah I in 654, who carried off the remains of the Colossus of Rhodes. The island was captured[clarification needed] by the Arabs before 674 as part of their attack on Constantinople. When their fleet was destroyed by storms and Greek fire, the island was evacuated. In 715 the Byzantine fleet launched a rebellion at Rhodes, which led to the installation of Theodosios III on the Byzantine throne
From the early 8th to the 12th centuries, Rhodes belonged to the Cibyrrhaeot Theme of the Byzantine Empire, and a center for shipbuilding and commerce. In circa 1090, it was occupied by the Muslim forces of the Seljuk Turks, not long after the Battle of Manzikert. Rhodes was recaptured by the Emperor Alexios I Komnenos during the First Crusade.
As Byzantine central power weakened under the Angeloi emperors, in the first half of the 13th century, Rhodes became the center of an independent domain under Leo Gabalas and his brother John, until it was occupied by the Genoese in 1248–1250. The Genoese were evicted by the Empire of Nicaea, after which the island became a regular province of the Nicaean state (and later of the restored Byzantine Empire).
In 1309, the Byzantine era came to an end when the island was occupied by forces of the Knights Hospitaller. Under the rule of the newly named "Knights of Rhodes", the city was rebuilt into a model of the European medieval ideal. Many of the city's famous monuments, including the Palace of the Grand Master, were built during this period.
The strong walls which the Knights had built withstood the attacks of the Sultan of Egypt in 1444, and a siege by the Ottomans under Mehmed II in 1480. Eventually, however, Rhodes fell to the large army of Suleiman the Magnificent in December 1522. The few surviving Knights were permitted to retire to the Kingdom of Sicily, from where they would later move their base of operations to Malta. Rhodes was thereafter a possession of the Ottoman Empire (see Sanjak of Rhodes) for nearly four centuries.