Originea numelui actual al orasului este subiectul multor controverse si pluteste în legenda; singurul lucru care se poate spune cu certitudine este ca numele vine de la slavonescul "kralj" (rege, crai). Dupa unii, numele ar veni de la Craiul Iovan (Ionita Asan), mezinul fratilor Petru si Asan, care devine pentru o perioada împarat al imperiului vlaho-bulgar, dar care, potrivit cronicii grecesti a lui Nicetas Choniates Akominatos, este nevoit sa se refugieze la sfârsitul domniei la nord de Dunare, unde devine "domn peste niste vlahi din neamul lui". Teoria potrivit careia Craiova devine capitala noii formatiuni pe care a întemeiat-o el este sustinuta de cercetatori ca L. Candea si V. Oghina, dar si de unele legende locale legate de lacul Craiovita si fata craiului înecata. Bogdan Petriceicu-Hasdeu fixeaza originile numelui orasului în epoca cneazului Ioan, care apare pe Diploma Ioanitilor, cnezat înghitit apoi de voievodatul lui Litovoi. Exista si o alta legenda locala potrivit careia, în dealul Sf. Dumitru, un oarecare Iovan, a descoperit în timp ce sapa o fântâna un mare tezaur si a devenit rege peste craioveni. S-a pastrat pâna in zilele noastre în satele din jurul Craiovei (pe dealul Bucovatului si Palilula) expresia "norocos ca Iovan". Sub acest nume, asezarea Craiovei apare mai întâi în inscriptia de pe mormântul lui Vladislav I, apoi la 1 iunie 1475, într-un hrisov al domnului Laiota Basarab. În afara denumirii antice, Pelendava si a numelui actual(Craiova), localitatea a mai purtat începând cu secolele VII-VIII denumirea latina Ponsiona (pod peste Jiu) denumirea aflata pe o inscriptie gasita pe un fragment de stela în apropierea castrului Pelendava datata din secolul al VII-lea, a primit o confirmare de extrema importanta în ultimii ani, într-o harta alcatuita în preajma bataliei de la Nicopole (1396), inclusa într-un manuscris ce se pastreaza la Biblioteca Nationala de la Paris.Aceast document, relevat istoriografiei românesti,prin bunavointa ministerului francez al cultelor, probeaza continuitatea asezarii Craiovei.