Stone Age remains have been found nearby in the Sakkos cave, in Skala and in the Mounda Bay area.

At nearby Mavrata there is a tomb from the Mycenaean period while Roman remains visible just behind the main Agia Barbara beach indicate settlement in Kateleios over 2000 years ago.

Until quite recently Kato Kateleios was a small collection of fishermen's houses and huts, some of which are still inhabited, and the main town was further up in the valley, at Ano Katelios.

Tourism development in recent years saw the construction of restaurants, homes, and rented apartments near the sea-front, which is now considered to be the main settlement of Katelios.

Sea turtle nests in this area have been monitored and protected since 1988, while an environmental station operates at the town's old school.