L’église basilique du port (Βασιλική του λιμένος) avait été bâtie au Ve ou au VIe siècle après JC : c’était probablement l’un des premiers édifices chrétiens érigés sur l’île de Kos, où le christianisme avait été établi au IVe siècle, comme en témoigne la participation de l’évêque Meliphron de Kos à des séances du premier concile œcuménique tenu à Nicée en Bithynie en 325.
La basilique paléochrétienne du port était un édifice à trois nefs séparées par des colonnes de granit à fût lisse ; l’église était couverte d’une toiture à charpente de bois. La nef centrale, qui était la plus large, se terminait par une abside semi-circulaire à l’extrémité est. À l’entrée de l’église se trouvait un atrium ouvert entouré sur trois côtés par des portiques, le portique de l’ouest étant à double colonnade. Depuis l’atrium, un escalier sur le côté menait au narthex tripartite. L’église proprement dite (naos) avait un sol en mosaïque. Sur le côté droit se trouvait un baptistère. La basilique avait une longueur de 62 m et une largeur de 23,5 m, ce qui en faisait l’une des plus grandes basiliques de la Méditerranée au moment où elle fut construite.
La basilique, dont les fondations sont conservées, avait été construite sur les vestiges et avec les matériaux de la stoá du port et de la jetée est, qui avaient été comblées pour créer un remblai artificiel, de sorte que la basilique dominait le quartier du port. Près d’un millénaire plus tard, les ruines de la basilique servirent de carrière aux Chevaliers Hospitaliers de Saint-Jean pour l’édification du château de Nerantzia et du mur de fortifications du bourg médiéval. On retrouve des colonnes de la basilique dans les plafonds des entrées extérieure et intérieure du château.
Une église basilique se trouvait dans la zone archéologique de l’ouest. Elle avait été construite après le tremblement de terre de 469 après JC, là où se trouvait le frigidarium (bains froids) des thermes romains de l’ouest. L’église avait trois nefs avec, à l’est, une grande arche en demi-cercle qui comprenait un amphithéâtre où le clergé siégeait. L’autel était soutenu par cinq colonnes en forme de cône dont on peut encore voir les bases aujourd’hui. La basilique a probablement été détruite par le tremblement de terre de 554 après JC.
Une autre basilique se trouvait dans la zone archéologique de l’ouest. Elle avait été construite après le tremblement de terre de 469 à l’emplacement du caldarium (bains chauds) des thermes romains de l’ouest. De l’édifice seuls quelques éléments architecturaux ont été conservés, mais de nombreuses pièces de marbre, parmi lesquelles l’impressionnante chaire, sont conservées à l’intérieur du Château des Chevaliers. Le sol de la basilique montre des fragments bien conservés de mosaïques ; cependant les plus belles de ces mosaïques ont été transférées, par les Italiens, dans le Palais des Grands Maîtres à Rhodes.
Au sud de la basilique se trouve un baptistère de forme cylindrique. Ces fonts baptismaux ont été restaurés sous la domination italienne. La basilique et le baptistère ont probablement été détruits par le tremblement de terre de 554 après JC.