Naxos Town, Restaurant Palatino Naxos town has a lot of really good restaurants. I think it is the island in Greece where I´ve found the most real good restaurants. Restaurant Palatino here on the picture is one of them, situated between two houses in the harbour area. Margaretha and I eat here several times. They have greek and italian food – really good.