Nel periodo della guerra di Troia, X secolo a.C., la regina delle amazzoni Pantasilea «rimase uccisa in battaglia da Achille, Cleta sua nutrice, che l'amava con tenerezza, nell'udire la triste notizia, posta su una nave e accompagnata da molta gente, partì col pensiero di poterle dare onorata sepoltura». Così, Cleta, ancella di Enea «come fu nei nostri mari scese a terra e o perché trovò impossibile compiere il pietoso ufficio o forse perché le piacesse l'amenità del sito decise di non passare più oltre, vi si fermò ed edificò la città che dal suo nome si chiamò Cleta».

«La città crebbe di popolo e di forze», tanto che all'epoca dello splendore della Magna Grecia entrò in guerra con Crotone (anno 16 a.C.). I Crotoniati, con un esercito, uccisero la regina la quale prima di morire ebbe ad esprimere il desiderio che tutte le regine che avrebbero regnato dopo di lei, portassero il suo nome; così «tutte le regine della città furono dette Cleta».

L'antica Cleto, centro importante della costa nel Medioevo, durante la dominazione normanna mutò il suo nome in Pietramala (1220 Guido di Pietramala e suo figlio Ruggero, 1239 Iacobus De Petramala, 1269 Castri Pietramala, 1310 Pietramala) e il nome rimase tale dal XII secolo al 1862, quando per decreto del 4 gennaio 1863 diventava Cleto.

Anche sul nome Pietramala le congetture sono molteplici, oltre che alla possibilità che il nome derivi dalla famiglia feudataria, si pensa che abbia qualche legame con la posizione: Pietramala nel senso di "pietra dura", cattiva, come scrive il Padula: «Pietra gande, pietra inaccessibile a guisa di Piramide, (…) le sole formiche possono salire in Pietramala». C’è ancora un’altra versione che i nativi sono soliti raccontare e che il Padula riporta nei suoi scritti: «Un vescovo essendovi rotta una gamba, volle che si chiamasse Pietramala».

L'origine di Cleto affonda le radici nella leggenda di Cleta e nel mito delle Amazzoni, le sacerdotesse guerriere della dea Atena. La leggenda narra di Pentesilea, regina della Amazzoni andata in aiuto dei Troiani ed uccisa da Achille, e della nutrice di Pentesilea, Cleta, la quale, saputo che la sua regina si trovava a Troia, si mette in mare per raggiungerla, ma durante la navigazione venti contrari la spingono sulle coste della Calabria, dove approda e fonda una città che prende il suo nome.