In the village of Nea Fokea stands what is perhaps the best-preserved of all the towers in Halkidiki,
the Byzantine tower of the namesake village.
The Tower in Nea Fokea, also known as St. Paul’s Tower holds a dominant position on the hill at the right side of N. Fokea’s port. The tower has a base of 50 sq.m., with a dimension of 7X7 meters and a height of 17 meters and it’s an old Byzantine fortress that is likely to have been built in 1407, and partially destroyed by fire in 1821. It is built of the materials of ancient buildings. Its purpose was the protection of farmers working in the "metochi" of St Paul's Monastery.
The tower rises majestically in an area that has been inhabited since ancient times; there is proof of an important settlement that dates back to 5000 BC. These times the sea level was at least 10m lower and the coastline far deeper which led to the result that the hill appeared far higher than it does today.
The Metochi around the tower was related to the Mount Athos monastery Agios Pavlos, gradually developed after the publication of the gold bullion of John VII Palaiologos in February 1407. Palaiologos was a "Despot" of the semi-autonomous Thessaloniki. According to these alternative sources, the tower was subsequently built during this time.