Originea si trecutul cetatii Deva isi au povestea lor, cunoscuta din negura vremurilor si din trecutul mai apropiat fie in forma legendara, fie istorica. Povestea legendara, creatie a imaginatiei populare, are mai multe variante.
- Una din legende spune ca muntii si plaiurile din partile Devei erau stapanite odinioara de 3 surori, fete de uriasi, toate mandre si puternice cum nu s-a mai pomenit. Odata se hotarara sa faca ele fiecare cate o constructie care sa puna lumea in mirare si uimire si sa ramana o amintire pe vecie. Astfel sora cea mica facu cetatea Deva, cea mijlocie scaldatoarea Calan si cea mare cetatea Uroiului. Si cand soarele apunea, luandu-si ramas bun de la valurile argintii ale Muresului si Streiului, dand cel din urma sarut piscurilor Tarii Hategului, pe cele doua varfuri de deal straluceau doua cetati minunate, iar in valea Streiului statea gata o scaldatoare scobita in stanca, cu apa calda si curate ca lacrima induiosarii.
Cea mai frumoasa realizare fu cetatea Uroiului, a fetei celei mai mari. Dar aceasta mandrindu-se peste masura cu realizarea ei fu pedepsita pentru trufie, pe cand celelalte surori fura modeste. Asa s-a intamplat ca intr-o noapte un vifor naprasnic nimici total cetatea Uroiu, ingropand sub ruinele ei si pe semeata stapana, iar cetatea Devei si Baia de la Calan au ramas pana astazi.
- Alta legenda arata ca Cetatea Devei, Uroiul si cea din Colt au fost ridicate de trei zane cu parul de aur si fete de urias. Surorile zane traiau foarte armonios si cetatile lor erau legate cu un pod de aur. Dar cu timpul zana din cetatea Colt, situate la poalele muntilor Retezat, se dusmanii cu celelalte surori. Atunci zana din cetatea Uroiului fiind mai razbunatoare, voi sa distruga cetatea zanei de la Colt si arunca o mistrie uriasa spre cetatea rivalei sale. Dar in aspra sa manie a nimerit varful muntelui Retezatul.

- Exista o legenda care zice ca cetatea Deva este gratia unor pitici harnici si geniali, care locuiau prin alte locuri, dar o vizitau din 7 in 7 ani sa vada daca mai exista. In lipsa lor un balaur cu 7 capete s-a furisat in cetate. Balaurul n-a putut fi alungat decat cu ajutorul lui Iorgu Iorgovan, un Hercule al tarii noastre. Urmarit balaurul s-a refugiat intr-o pestera de la Portile de Fier, langa Dunare, unde Iorgovan l-a ajuns si l-a ucis. Dar sangele plin cu venin al balaurului l-au supt mustele si astfel s-a format musca columbaca, cunoscuta pe aici ca iesind din aceasta pestera.
- A patra legenda povesteste ca ziditorul cetatii Deva este un mester Manole, cunoscut in versiunea maghiara ca Clement sau Kelemen, zidarul care impreuna cu 12 ortaci s-au legat sa zideasca cetatea pentru o jumatate merta de aur si alta de argint. Apucati la lucru nu avura niciun spor fiindca ce se zidea ziua, se surpa noaptea si ce lucrau noaptea se surpa dimineata. Disperati si in credinta unei reusite ei facura legamant sa arda sotia care va sosi prima in ziua urmatoare iar cenusa sa fie amestecata in tencuiala. Napasta a cazut pe sotia mesterului, care a fost jertfita si astfel cetatea s-a putut ridica.