Originea și trecutul cetății Deva își au povestea lor, cunoscută din negura vremurilor și din trecutul mai apropiat fie în formă legendară, fie istorică. Povestea legendară, creație a imaginației populare, are mai multe variante.
1. Una din legende spune că munții și plaiurile din părțile Devei erau stăpânite odinioară de 3 surori, fete de uriași, toate mândre și puternice cum nu s-a mai pomenit. Odată se hotărâră să facă ele fiecare câte o construcție care să pună lumea în mirare și uimire și să rămână o amintire pe vecie.
Astfel sora cea mică făcu cetatea Deva, cea mijlocie scăldătoarea Călan și cea mare cetatea Uroiului. Și când soarele apunea, luându-și rămas bun de la valurile argintii ale Mureșului și Streiului, dând cel din urmă sărut piscurilor Țării Hațegului, pe cele două vârfuri de deal străluceau două cetăți minunate, iar în valea Streiului stătea gata o scăldătoare scobită în stâncă, cu apă caldă și curate că lacrima înduioșării.
Cea mai frumoasă realizare fu cetatea Uroiului, a fetei celei mai mari. Dar această mândrindu-se peste măsură cu realizarea ei fu pedepsită pentru trufie, pe când celelalte surori fură modeste.
Așa s-a întâmplat că într-o noapte un vifor năprasnic nimici total cetatea Uroiu, îngropând sub ruinele ei și pe semeață stăpână, iar cetatea Devei și Baia de la Călan au rămas până astăzi.
2. Altă legendă arată că Cetatea Devei, Uroiul și cea din Colț au fost ridicate de trei zâne cu părul de aur și fete de uriaș. Surorile zâne trăiau foarte armonios și cetățile lor erau legate cu un pod de aur.
Dar cu timpul zâna din cetatea Colț, situate la poalele munților Retezat, se dușmanii cu celelalte surori. Atunci zâna din cetatea Uroiului fiind mai răzbunătoare, voi să distrugă cetatea zânei de la Colț și aruncă o mistrie uriașă spre cetatea rivalei sale. Dar în aspră sa mânie a nimerit vârful muntelui Retezatul.
3. Există o legendă care zice că cetatea Deva este grația unor pitici harnici și geniali, care locuiau prin alte locuri, dar o vizitau din 7 în 7 ani să vadă dacă mai există. În lipsa lor un balaur cu 7 capete s-a furișat în cetate.
Balaurul n-a putut fi alungat decât cu ajutorul lui Iorgu Iorgovan, un Hercule al țării noastre. Urmărit balaurul s-a refugiat într-o peșteră de la Porțile de Fier, lângă Dunăre, unde Iorgovan l-a ajuns și l-a ucis. Dar sângele plin cu venin al balaurului l-au supt muștele și astfel s-a format musca columbacă, cunoscută pe aici ca ieșind din această peșteră.
4. A patra legenda povestește că ziditorul cetății Deva este un meșter Manole, cunoscut în versiunea maghiară ca Clement sau Kelemen, zidarul care împreună cu 12 ortaci s-au legat să zidească cetatea pentru o jumătate merța de aur și alta de argint.
Apucați la lucru nu avură niciun spor fiindcă ce se zidea ziua, se surpă noaptea și ce lucrau noaptea se surpa dimineață. Disperați și în credința unei reușite ei făcură legământ să ardă soția care va sosi prima în ziua următoare iar cenușa să fie amestecată în tencuiala.
Năpasta a căzut pe soția meșterului, care a fost jertfită și astfel cetatea s-a putut ridica.