Al final del IIIe siglo después de J. - C., se compartió al Imperio romano en dos por el emperador Diocleciano, y, en 395, a la muerte de Théodose 1.o, se dividió definitivamente en Imperio romano de Occidente e Imperio romano de Este. La isla de Kos, al igual que Grecia, formará en adelante parte del Imperio de Oriente; lo permanecerá durante ocho siglos
El Imperio romano se había convertido en cristiano bajo el reino de Constantino I el Grande (306 - 337 después de J. - C.) que fundó la ciudad de Constantinopla sobre el lugar de la antigua ciudad de Bizancio. En este Imperio bizantino en pleno desarrollo, Kos se volvió la sede de un obispado y contó a una población de 160.000 habitantes.
En 469, los espléndidos edificios de la ciudad grecorromana y el Asclépiéion fueron dañados severamente por un terremoto, luego por otro en 554.
Al principio del Ve siglo y hasta el principio del VIIe siglo, algunas hordas crueles atacaron la isla (Godos, Vándalos, Búlgaros, Avaros etc). En la segunda mitad del VIIe siglo, fueron los Árabes que saquear la isla.
A pesar de los saqueos y las destrucciones causadas por los seísmos, los vestigios arqueológicos datando de este tiempo paléochrétienne son impresionantes. Los monumentos más importantes del tiempo son, sin duda alguna, las numerosas grandes basílicas cuyas ruinas se descubrieron en numerosas zonas alrededor de la isla de Kos. La mayoría de entre ellas se decora de mosaicos impresionantes, producidos por los talleres locales reelegidos para su calidad artística. Además a lo largo de las costas de la isla (en las localidades actuales de Kefalos, Kardamena y Mastihari), se descubrieron grandes colonias de asentamiento; incluían edificios espaciosos y calles. Esta prosperidad finalizó con las incursiones árabes que obligaron la mayoría de los habitantes a refugiarse dentro de la isla.
Al principio del XIIe siglo, Kos formó parte de las regiones reivindicadas por la República de Venecia. En 1204, después de la conquista de Constantinopla por los Cruzados, Kos y las otras islas del Dodecaneso dejaron de formar parte del Imperio bizantino.
