Legende i predanja su vezana za objekte koji čine kulturnu baštinu grada Vranja.

Najpre postoji legenda za naziv grada Vranje, koja glasi da se ono u starini zvalo Golubinje i to do propasti naše pod Turke, po imenu vojvode Golubića koji je upravljao Vranjem. Golubić je imao ženu Vranu i kad je on sa knezom Lazarom poginuo na Kosovu, umesto njega zavlada njegova žena Vrana, a Golubinje se prozva imenom Vranje.

Zatim legenda o Žutom cveću, koja se odnosi na period Prvog svetskog rata, kada su se francuski vojnici obratili jednoj baki na francuskom. Baka je zalivala cveće i nije dobro čula niti razumela, mislila je da kažu božur (Cvet crvene boje), a ne Bonžur (Dobro jutro), pa ih je ispravila da njeno cveće nije božur, već žuto cveće. Zato je žuta boja simbolična za Vranja.

Simbol grada je i Beli most, kojeg prati legenda o velikoj i tragičnoj ljubavi između Ajše i Stojana.

Postoji i legenda za Markovo kale, da je to nekadašnji grad-tvrđava junaka Kraljevića Marka, koji je po njemu dobio ime. Marko je sa svojim Šarcem sa tog mesta napravio podvig na istok, gde je zaplakao pa otuda naziv planinskog masiva Pljačkovica, zatim na zapad, tu se prekrstio i planina je dobila naziv Krstilovica.

Poznata je legenda o Krstatoj džamiji, koja glasi da su Turci izgradili minaret na crkvi Svete Petke, ali nadprirodne sile su rušile taj minaret sve dok nisu Turci na njegov vrh stavili krst.

Zatim, tu su i legende posvećene česmama u gradu iz turskog perioda. I to česma Đerenka koja je izgrađena u sećanje na turskog mladića Đerzeleza, koji je bio zaljubljen u crnokosu srpsku devojku. I Mačkina česma koja govori o tragediji srpske majke Dimane.

Svaka od ovih legendi sadrži zanimljivu priču i ima originalnu težinu, kada se priča ispred samih objekata.