Elhamra'ya dair en bilinen efsanelerden biri, Aslanlar Avlusu çevresinde saklı olduğu söylenen hazinelerle ilgilidir. Bazı anlatılara göre, saray terk edilirken altın ve mücevherler gizli odalara, yer altı galerilerine veya aslan heykellerinin içlerine saklanmış ve hazine bugüne kadar bulunamamıştır. Arkeolojik veriler bu hikâyeyi desteklemese de, ziyaretçilerin hayal gücünde güçlü bir yer tutar.
Bir diğer popüler tema, trajik aşk hikâyeleridir. Sarayda yaşayan prensesler, askerlere veya düşman prenslere âşık olur; yasak ilişkiler, ihanet ve cezalandırma motifleriyle süslenen hikâyeler, özellikle 19. yüzyıl romantik edebiyatında sıkça işlenir. Bu öyküler, sarayın incelikli mimarisine karışmış bir hüzün duygusu üretir.
Gizli geçitler, kaybolan kapılar ve gece ortaya çıktığı söylenen hayaletler de Elhamra söylencelerinin vazgeçilmez parçalarıdır. Özellikle boş bırakılmış bazı kuleler ve loş koridorlar, bu tür anlatılar için elverişli sahneler sunar. Ziyaretçi bu mekânlardan geçerken, tarihî gerçeklik ile hayal dünyası arasındaki sınır bulanıklaşır.
Washington Irving'in "The Alhambra" adlı kitabı, bu yerel söylenceleri derleyip yeniden kurgulayarak uluslararası okura taşıyan en önemli eserlerden biridir. Kitapta yer alan hikâyeler, bugün bile rehber anlatılarını, film ve dizileri, hatta popüler kültürdeki Elhamra imgelerini etkilemeye devam etmektedir.