Nea Fokea (pop. 2,000), about 12 km south of Kassandra's most northerly village, Nea Potidea, and 65 or so from Thessaloniki, has all of the things you like in a Greek seaside village: it has the picturesque little harbor busy with the coming and going of fishing boats and small pleasure craft, it has the beautiful views from its seaside promenade, its sandy beach with its sun beds and umbrellas, and thousands of summer season visitors. It has its cafes and eateries on the seaside, its charming, traditionally narrow village streets, and its various types of rooms for let.
But it also has some things of historical import, and a couple of things you don't see much in Halkidiki: for one, it has the tall, rectangular, cut stone, Byzantine-era St. Paul's Tower standing on a bluff overlooking the sea and the harbor, and secondly, it has the cave church of St. Paul.
The cave church St. Paul, where local legend has the Apostle Paul staying for awhile. The fact that Nea Fokea would have represented a 140-km detour for the apostle on his trek from Philippi to Thessaloniki is of little import.
The likelihood, however, is great that the cave was a place of worship even long before Paul visited Greece, as most Greek caves were. They represented a labor-free way to keep out of the weather, and caves exude a sort of mysterious atmosphere anyway which helps if you're interested in communicating with the spiritual realm.
The church cave has a hewn stone facade against the face of the hill the cave is on. The stone work is quite old. There is a cross chiseled into the stone above the entrance. Inside is a dark, narrow, whitewashed tunnel cut from the rock of the hillside, leading to a small room equipped with pews, holy water, candles, and icons: this is the tiny church. Another passage takes you deeper into the cave, to a space where they say Paul slept. Before the name change to Nea Fokea in 1925 when refugees from Fokea, Anatolia, settled here, the place was known as St. Paul.
During the Byzantine era Nea Fokea was home to the St. Paul monastery (indicating that, true or not, the legend of Paul stopping by is an old one) The monastery building, which is right next to the tower, is a low stone structure with a few window openings.
The tower looks exactly like the tower in the Tower of St. Paul monastery near the southwestern end of the Mt. Athos peninsula. Which leads one to guess that the monastery and tower were sort of copies of the monastery and tower on Mt. Athos, although the Mt. Athos monastery is far more spectacular, and much larger.
The tower overlooks the scenic little harbor with its mole, and rip-rap breakwater, and has visual command of the whole area because of its 15-meter height and its being on the highest piece of ground around. In 1821, Emmanuel Pappas, a hero of the Greek revolution, gathered men together at the Tower to organize and prepare to do battle their Ottoman Turk overlords.
Evidence exists for the continuous inhabitation of the location of Nea Fokea since pre-historic times. Small sculpted objects from Classical Greece have been found, and the foundations of houses from the Roman period have been excavated.
So for a small place, there's a lot to see in Nea Fokea. It's a quiet town, meaning there's not a lot of night life, which is just the way a lot of tourists like it.