Nerja har en lang historie, hvilket de primitive malerier, der blev fundet i de berømte Nerja-huler, som blev opdaget i 1959, er et bevis på. Disse huler menes nu kun at være en af indgangene til en række sammenkoblede hulrum, der strækker sig mange kilometer ind i bjergene mellem Nerja og Granada, og som måske endnu kan vise sig at være et af de mest omfattende uudforskede systemer i Europa. Besøgende i grotterne vil kunne se resterne af en af de gamle indbyggere i Nerja.
Romerne byggede her tre bosættelser, herunder Detunda, som man nu kan se store rester af. Området blev senere overtaget af araberne i begyndelsen af det 8. århundrede. Under maurerne var byen kendt som Narixa, hvilket betyder “rigelig kilde”, hvorfra det nuværende navn stammer.
Dets landbrugs- og silkeprodukter siges at have været berømt i hele den muslimske verden og på markederne i Damaskus allerede i det 10. århundrede.
Balcón de Europa, en mirador eller et udsigtspunkt, der giver en fantastisk udsigt over havet, ligger i centrum af den gamle bydel. Man mener populært sagt, at dens navn er blevet opfundet af kong Alfonso XII, som besøgte området i 1885 efter et katastrofalt jordskælv og blev betaget af scenen. Den lokale folklore fortæller, at han stod på det sted, hvor Balcón nu står, og sagde: “Dette er Europas balkon”. Det siges, at lokale arkivdokumenter viser, at navnet stammer fra før dette besøg, men det har ikke forhindret myndighederne i at opstille en statue i naturlig størrelse (og meget fotograferet) af kongen ved rækværket.
Balcón-området var oprindeligt kendt som La Batería, en henvisning til det kanonbatteri, der fandtes der i et befæstet tårn. Denne opstilling og et lignende tårn i nærheden blev ødelagt under halvøkrigen. I maj 1812 støttede de britiske skibe Hyacinth, Termagant og Basilisk de spanske guerillaer på kysten ved Granada mod franskmændene. Den 20. maj åbnede Termagant eller Hyacinth ild, og forterne blev ødelagt. To rustne kanoner, der er placeret for enden af Balcón, er et minde om disse voldsomme tider. De store klippeklumper, resterne af La Batería, der er synlige i havet for enden af Balcón, er et yderligere bevis på denne aktion.
