No fim o IIIe do século após J. - C., o Império romano foi compartilhado em dois pelo imperador Dioclétien, e, em 395, à morte de Théodose 1, definitivamente foi dividido em Império romano de Ocidente e Império romano de Oriente. A ilha de Kos, da misma maneira que a Grécia, fará doravante parte do Império de Oriente; permanecê-lo-á durante oito séculos
O Império romano tinha-se tornado cristão sob o reino Constantin o Grande (306 - 337 após J. - C.) que fundou a cidade de Constantinopla sobre o sítio da antiga cidade de Bizâncio. Neste Império bizantino em cheio desenvolvimento, Kos tornou-se a sede de um bispado e contou uma população de 160.000 habitantes.
Em 469, magníficas as construções da cidade gréco-romaine e o Asclépiéion foram danificadas severamente por um tremor de terra, seguidamente por outro em 554.
Ao início do século V e até ao início do VIIe século, a ilha foi atacada por hordas bárbaras (Goths, Vândalo, Búlgaros, Avaros et cetera). Na segunda metade do VIIe século, foram os Árabes que saquearam a ilha.
Apesar das pilhagens e as destruições causadas pelos sismos, os vestígios arqueológicos que datam desta época paleocristã são impressionantes. Aos monumentos mais importantes da época são, sem nenhuma dúvida, numerosos os grandes basílicas cujas ruínas foram descobertas numerosas em zonas em redor da ilha de Kos. A maior parte entre elas é decorada de mosaicos impressionantes, produzidos pelos ateliers locais rebatizados para a sua qualidade artística. Além disso, ao longo das costas da ilha (nas localidades atuais de Kefalos, de Kardamena e de Mastihari), grandes colónias de povoamento foram descobertas; compreendiam construções espaçosos e ruas. Esta prosperidade tomou fim com as incursões árabes que forçaram a maior parte dos habitantes a refugiar-se dentro da ilha.
Ao início o XIIe do século, Kos fez parte das regiões afirmadas pela República de Veneza. Em 1204, após a conquista de Constantinopla os Cruzado, Kos e as outras ilhas de Dodecaneso cessou fazer parte do Império bizantino.
