Staří Řekové věřili, že na Chalkidiki žijí obludní a fousatí obři. Ti prý byli odvěcí nepřátelé řeckých bohů. Ale vlivem kouzelné rostliny byli nezranitelní. Jednoho dne se rozhodli sesadit nejvyššího boha Dia. Chtěly vládnout místo něj, avšak porazil je bájný hrdina Hercules, známý svým napůl božským a napůl lidským původem.
Určitě vás také napadla souvislost mezi názvy poloostrovů, třech prstů Chalkidiki, Sithonia, Athos, Kassandra. Tak tedy Sithonia je pojmenována podle syna Poseidona. Athos je název kamene, který byl vrhán po bozích bájnými obry. Říká se, že velikost toho kamene je stejná jako nejvyšší hora Chalkidiki – hora Athos.
A Kassandra, u ní je to složitější. Jedna teorie je, že jméno nosil nástupce Alexandra Makedonského, který na Chalkidiki žil. Také je druhá teorie, ta říká, že název se odvozuje od starověké věštkyně jménem Kassandra.