The castle o Messaria is halfway between Megalo Chorio and Mikro Chorio of Tilos. It was built in 1366 by the knights of Rhodes. It is near the famous Charkadio Cave, where the fossils of a pygmy elephant were unearthed in 1971.

Tilos was occupied by the knights of the Order of St. John of Rhodes since 1310. In 1366 the island was granted as a feud to Barello Assanti d' Ischia who had the obligation to fortify the island. There are 7 castles in Tilos, all of which were either built or repaired during the Ioannite period.

One of the first castles of this period was the castle of Messaria. The fortress protected the road to the fertile plains of the island. Within its massive walls, the ruins of several buildings and of a little church are found. The remains of a Byzantine settlement and of small chapels dating back to the 13th century can be found close to the fortress. The walls of the churches are covered with frescoes.