Aan het einde van IIIe eeuw na J. - C., werd het Romeinse Imperium in twee door de keizer Diocletianus gedeeld, en, in 395, aan de dood van Théodose Eerste, werd hij definitief in Romeins Imperium van Westen en Romeins Imperium van Oosten verdeeld. Het eiland Kos, zal zoals heel Griekenland, voortaan deel van het Imperium van Oosten uitmaken; zij gedurende acht eeuwen zal het blijven
Het Romeinse Imperium was christelijk onder de regering van Constantinus I Groot geworden (306 - 337 na J. - C.) die de stad Constantinopel op de plaats van de oude stad Byzantium baseerde. In dit Byzantijnse Imperium in volle ontwikkeling, werd Kos de zetel van een bisdom en telde een bevolking van 160.000 inwoners.
In 469, werden de prachtige gebouwen van de Griekse-Romeins stad en Asclépiéion streng door een aardbeving, vervolgens door een ander in 554 beschadigd.
Aan het begin van Ve eeuw en tot het begin van VIIe eeuw, werd het eiland door groffe horden (Bulgaars, Gierig Goths, Vandalen, enz) aangevallen. In de tweede helft van VIIe eeuw, waren het de Arabieren die het eiland plunderden.
Ondanks de plunderingen en de vernielingen die door de aardbevingen worden veroorzaakt, zijn de archeologische overblijfsels die van dit tijdperk paléochrétienne dateren, indrukwekkend. De belangrijkste monumenten van het tijdperk zijn, zonder enige twijfel, de talrijke grote basilieken waarvan de ruïnes in talrijke zones rond het eiland Kos werden ontdekt. Het merendeel onder hen wordt van indrukwekkende mozaïeken versierd, die door de plaatselijke werkplaatsen worden geproduceerd, renommés voor hun artistieke kwaliteit. Bovendien langs de kusten van het eiland (in de huidige plaatsen van Kefalos, Kardamena en Mastihari), werden grote bevolkingskolonies ontdekt; zij omvatten ruime gebouwen en straten. Deze welvaart eindigde met de Arabische invallen die het merendeel van de inwoners verplichtten om binnen het eiland te vluchten.
Aan het begin van XIIe eeuw, maakte Kos deel van de gebieden uit die door de Republiek van Venetië worden geëist. In 1204, na de verovering van Constantinopel door Gekruist, Kos en de andere eilanden van de Dodecanese hielden op met deel van het Byzantijnse Imperium uit te maken.