À la fin du IIIe siècle après JC, l’Empire romain fut partagé en deux par l’empereur Dioclétien, et, en 395, à la mort de Théodose Ier, il fut définitivement divisé en Empire romain d’Occident et Empire romain d’Orient. L’île de Kos, comme toute la Grèce, fera désormais partie de l’Empire d’Orient ; elle le restera pendant huit siècles.
L’Empire romain était devenu chrétien sous le règne de Constantin le Grand (306 - 337 après JC) qui fonda la ville de Constantinople sur le site de l’ancienne ville de Byzance. Dans cet Empire byzantin en plein essor, Kos devint le siège d’un évêché et compta une population de 160 000 habitants.
En 469, les magnifiques bâtiments de la ville gréco-romaine et de l’Asclépiéion furent sévèrement endommagés par un tremblement de terre, puis par un autre en 554.
Dès le début du Ve siècle et jusqu’au début du VIIe siècle, l’île fut attaquée par des hordes barbares (Goths, Vandales, Bulgares, Avares et cetera). Dans la seconde moitié du VIIe siècle, ce furent les Arabes qui saccagèrent l’île.
Malgré les pillages et les destructions causées par les séismes, les vestiges archéologiques datant de cette époque paléochrétienne sont impressionnants. Les monuments les plus importants de l’époque sont, sans aucun doute, les nombreuses grandes basiliques dont les ruines ont été découvertes dans de nombreuses zones autour de l’île de Kos. La plupart d’entre elles sont décorées de mosaïques impressionnantes, produites par les ateliers locaux renommés pour leur qualité artistique. En outre, le long des côtes de l’île (dans les localités actuelles de Kefalos, Kardámena et Mastihari), de grandes colonies de peuplement ont été découvertes ; elles comprenaient des bâtiments spacieux et des rues. Cette prospérité prit fin avec les incursions arabes qui contraignirent la plupart des habitants à se réfugier à l’intérieur de l’île.
Dès le début du XIIe siècle, Kos fit partie des régions revendiquées par la République de Venise. En 1204, après la conquête de Constantinople par les Croisés, Kos et les autres îles du Dodécanèse cessèrent de faire partie de l’Empire byzantin.