Palaiochori (Greek: Παλαιοχώρι) is a village in Chalkidiki, Greece, part of the municipality Aristotelis.

In 1793 the French ambassador in Thessaloniki Esprit-Marie Cousinéry visited Palaiochori as is documented in 3 pages of Voyage dans la Macédonie (ISBN 1421208806).

In the Civil War the village was again destroyed on 14 August 1948 by communist rebels.

Giorgos Zorbas was born in Kolyndros in Pieria before moving to Paleochori for work.

A central street is named after the leader of the Orthodox Church Bartholomew I who visited Paleochori in June 1999.