Milattan önce 32 yılında, efsanevi Mısır kraliçesi VII. Kleopatra ve sevgilisi, Romalı komutan Marcus Antonius, bu kıyılara ayak bastı. Kraliçe, turkuaz suların ve sarp kayalıklarla çevrili kıyıların büyüsüne öylesine kapıldı ki Antonius, tüm Kilikya bölgesini ona düğün hediyesi olarak sundu.
Ne var ki bir sorun vardı: Kleopatra, sahildeki kumu kraliyet ayakları için fazla kaba bulmuştu. Umutsuzca tutkun Antonius, kraliçesi için kusursuz bir sahil yaratmak üzere İskenderiye'den altın renkli özel kum getirmesi için altmış gemi gönderdi.
Bilim insanları, Kleopatra Plajı'ndaki kumun Türkiye'de eşsiz olduğunu doğrulamıştır. Her bir kum tanesi boyut ve biçim bakımından birbirinin aynısıdır, cilde yapışmaz ve dünyada yalnızca tek bir eşi vardır: Mısır İskenderiye'sinin sahilleri.
Rivayete göre Kleopatra her sabah kayalara oyulmuş doğal bir havuza yüzerek gidermiş. Yöre halkı, sudaki minerallerin onun efsanevi güzelliğinin sırrı olduğuna inanır. Bazıları, kraliçenin kalenin altındaki deniz mağaralarına hazineler sakladığına ve bu hazinelerin bugüne dek keşfedilmediğine inanmaktadır.
Tarihî kayıtlar, Kleopatra'nın Kilikya'yı gerçekten armağan olarak aldığını doğrulamaktadır; bu bilgi Roma arşivlerinde belgelenmiştir. Adını taşıyan kumların üzerinde gerçekten yürüyüp yürümediğiyse, romantik bir sır olarak kalmaya devam etmektedir.