Ten gevolge van de verzwakking van het Byzantijnse Imperium, maakte Vénitiens zich van het eiland Kos tegen 1306 meester. In 1315, verkochten zij het eiland aan de Gastvrije Ridders van Sint-Jan. Tot in 1336, werd het eiland nog tussen het Byzantijnse Imperium, Vénitiens en de Ridders van Sint-Jan betwist. Na deze datum controleerden de Ridders stevig het eiland Kos.
De middeleeuwse stad Kos, die door de Gastvrije Ridders wordt versterkt, bezette de zone omvat vandaag tussen de Boulevard van de Palmen (Λεωφόρος των Φοινίκων) en de Boulevard Hippocrates (Λεωφόρος Ιπποκράτους); zij omvatte minder van een kwart van de Griekse-Romeins antieke stad, dat wil zeggen alleen maar de zone van de haven en de oude agora, vervolgens bekend als de wijk Chora.
Grenzend aan het kasteel van Neratzia bevond een klein stadje zich waarvan het vestingwerk voor zelfs de bouw van de vesting was begonnen. Het is onder magistère van Jean Fernandez van Heredia (1376-1396) dat een hoge muur van geringe grootte, die met een weinig diepe sloot is omgeven, van 1391 tot 1396 werd gebouwd. Dit vestingwerk had ten doel de middeleeuwse stad tegen de aanvallen van de Turken van de sultan Bajazet Eerste te verdedigen.
Er blijft van deze versterkte ruimte slechts twee van de vijf deuren, Deur van het Zuiden en de bekende deur onder de naam van „Deur van de Toekenning“, twee omloop (aan de Zuidoost en zuidwesten hoeken van het stadje) en een kleine afdeling van de muur (onder de Plaats van de Plataan van Hippocrates).
De Deur van de Toekenning (Πύλη του Φόρου) benoemd, aan de zuidwesten hoek, werd aldus omdat de kooplieden, aan de Middeleeuwen, er de belasting moesten betalen om goederen in de middeleeuwse stad te verkopen. Pórta toú Fórou wordt, tegenwoordig, van prachtige bougainvillea bedekt.
De Kerk Saint-Jean-le-Nauclère
De kerk Saint-Jean-le-Nauclère (Άγιος Ιωάννης ο Ναύκληρος) werd aan het begin van XVe eeuw en in het begin gebouwd die aan heilige Jean-Doopsgezinde, de heilige werkgever van de Gastvrije Ridders van Sint-Jan worden gewijd, die het eiland op dat moment beheersten.
De kerk viel in ruïnes en, in 1943, werd zij verplaatst en hersteld. In 1947 werd de kerk aan de martelaar afkomstig uit Kos, heilige Jean-le-Nauclère gewijd. Jean was nauclère (dat wil zeggen de reder) verleidt door de Turken en veranderd aan de islam geweest. Hij zwoor vervolgens de islam af en verzekerde zijn christelijk vertrouwen; hij bleef het doen sinds de gevangenis na zijn arrestatie door de Turken: deze veroordeelden het ter dood door bûcher.