Chalkidiki is often mentioned in Greek mythology. It has been reported that the ancient name of Kassandra was Flegra, which means fireplace. It was the birthplace of the giants and it became a battlefield, when the giants tried to expel the gods from Mt Olympus. According to a myth, a giant, for the earthquakes of Engelados, was squashed under a piece of earth the gods threw at him and was buried under the Kassandra peninsula. But since the giants are immortal, occasionally he tried to free himself from the burden that squashed him and this is how earthquakes occur. Mount Athos was named after the giant Atho, who lifted and threw a whole mountain, as if it was a small stone, at the gods. Sithonia, according to mythology, has always been named after Sithonas, who was the son of Poseidon. He married the nymph Mende and they had a daughter, Pallene, after whom the Kassandra peninsula and one of its ancient cities were named. The mythical testimonies that followed came from the Trojan war period. Aeneas, leaving the ruined city of Troy, spent the winter near cape Karabournou, where he built a city which later took his name. It was at Kassandra that the Pellenians from Achaia also stopped on their way back from Troy. They had captivated Trojan women, who burnt down their ships, in order not to live in captivity. So the Pellenians were forced to live there and marry their slaves. It is believed that the peninsula took its second name from them.

The first traces of life on Chalkidiki appeared 700,000 years ago, according to the finds of the cave "Petralona". The first Greek emigrants arrived from Chalkida and Eretria during the Bronze Age, mainly for commercial purposes. In the beginning of the 5th century BC the Persians tried to occupy the area and the destruction of Mardonios's fleet is one of the most impressive historical events. Chalkidiki raised several important literary figures, such as the great philosopher Aristoteles who is believed to have been born at Stagira in 384 BC. During the Peloponnesian war, hundreds of fights and retaliations occurred in the area, and since 348 BC, after the siege and destruction of Olinthos by Philip the 3rd, Chalkidiki came under the Macedonian rule. It was conquered by the Romans, in 168 BC and during the Byzantine era suffered a number of invasions. The foundation of the first three monasteries of Agion Oros began in the 9th century and until the middle of the 14th century, most of Chalkidiki was under the Serbian rule of Stephanos Dousan. The Turks occupied it soon afterwards, and soon it became one of the most important centres of the Othoman Empire, while Agion Oros was enjoying special privileges at the time, being completely autonomous. Chalkidiki plays a leading part in the Greek Revolution of 1821, with the Serraian "Philiko" (of the Secret Society) Emmanuel Papas as a leader. The failure of the revolution in the area was followed by great slaughters and the extermination of its population. In 1822, Mechmet Passa invaded Chalkidiki and slaughtered 200 monks causing new disasters. In 1854, Tsamis Karatasos landed on Sithonia and began attacking the Turks. He then fled to Agion Oros and from there to southern Greece. At the end of the 19th century the whole of Macedonia was in danger from the Bulgarian expansion. In October 1912, Greek rebels expelled the Turkish custodians and declared its union to Greece. After 1922, a new page in the history of Chalkidiki was written, with the moving of thousands of refugees from Asia Minor and their settlement in the area.