Nema pouzdanih podataka kada i gde je formirano naselje i na čijim temeljima je iznikao grad Vranje. Pretpostavlja se da se to dogodilo u vreme Trako - Ilira (Rimljana), Vizantije, Grka ili Slovena koji su ove prostore naseljavali u VI i VII veku. Međutim, jedno je sasvim jasno: ovo je izuzetno važno geostrateško područje na kome su se od pamtiveka ukrstavali karavanski putevi. Tako da je najlakši put ka jednome i ka drugome, osvajače vodio put preko vranjskog pomoravlja.

Prvi pisani trag o Vranju ostavila nam je Ana Komnina, vizantijska princeza, još u XI veku, pišući o vladavini svoga oca cara Aleksija Komnina. Ona u knjizi „Aleksijada" kaže da je raški župan Vukan 1093. godine u svom osvajačkom pohodu stigao do Vranja i osvojio ga. Ne zadugo, on se pred moćnijom Vizantijom morao povući. Ona to opisuje ovako:

„Na to se Vukan osmeli i, kako nije preostalo nikoga da mu se suprotstavi, poče da pljačka susedne gradove i zemlje. I okolinu Skoplja potpuno opustoši, a delom i popali. Ali ne samo to, nego, zauzevši Polov i stigavši do Vranja, uništi i opustoši sve i odvuče otuda mnogo plena pa se vrati u svoju zemlju. “

Drugi put 1193. godine, Vranje je od Vizantije privremeno preoteo veliki raški župan Stefan Nemanja i pripojio ga srednjovekovnoj srpskoj državi. Ipak, u sastav srpske države Vranje je definitivno ušlo 1207. godine kada ga je osvojio Stefan Prvovenčani.

Interesantno je napomenuti da je prilikom raspada srpske srednjevekovne države, Vranje postalo samostalna oblast pod upravom kesara Uglješe, „Gospodara Vranja, Preševa i Kumanova“. Ova samostalna oblast nestala je posle Kosovske bitke, kada je Vranje ušlo u sastav države despota Stefana Lazarevića.

Raspadom srpske srednjovekovne države, Turci su Vranje osvojili 14. juna 1455. godine, i držali ga u svojim rukama sve do 31. januara 1878. godine, na svetog Antanasa, kada je varoš osvojila srpska vojska pod komandom generala Jovana Belimarkovića. Vranje je pod turskom vlašću bilo 422 godine. Grad je u Kneževini Srbiji dočekao slobodu sa nešto više od 8.000 stanovnika.

Početkom 20. veka, Vranje je imalo oko 12.000 stanovnika. Kao pogranični grad Kneževine/Kraljevine Srbije, služio je kao polazno mesto za četnike (komite) u Staru Srbiju. U to vreme, u gradu se nalazio i konzulat Osmanskog carstva.

U Balkanskim i dva svetska rata, Vranje i ovaj kraj ponovo su bili na meti osvajača. U Prvom balkanskom ratu, 1912. godine operacijama protiv Turaka, odavde su lično komandovali kralj Petar I Karađorđević, predsednik vlade Nikola Pašić, sa više ministara i generalštab sa načelnikom štaba Vrhovne komande vojvodom Radomirom Putnikom.

No, ovi prostori su, posebno u novoj istoriji, bili česta meta bugarskih osvajača koji su ovde počinili nečuvene zločine. U Prvom svetskom ratu, Bugari su okupirali Vranje 16/17. oktobra 1915. godine. Sloboda je tada plaćena sa 514 života na frontu i 335 nedužno streljanih.

U Drugom svetskom ratu, Nemci su u ovaj grad ušli 9. aprila 1941. godine, da bi ga 22. aprila predali u ruke bugarskim fašistima. Oni su u Vranju, za četiri godine, napravili prava zverstva - streljali su oko 700, a internirali 4.000 rodoljuba. U borbama je učestvovalo oko 12.000 boraca, od kojih 956 nije dočekalo slobodu 7. septembra 1944. godine.