Markovo Kale nalazi se oko 3,5 km severozapadno od Vranja, na strmom stenovitom grebenu koji okružuju planine Krstilovica i Pljačkavica. Ispod samog grada protiču Devotinska i Mala Reka. Markovo kale su držalo po redu: kaznac Miroslav (u vreme kralja Milutina), tepčija Kuzma i knez Baldovin (u vreme Stefana Dečanskog), župan Maljušat (u vreme cara Dušana) i ćesar Uglješa (početak 15. veka).
1412. godine, tvrđavu je osvojio turski sultan Musa. Markovo kale se nalazi na starom putu Leskovac-Vranje iznad koga se izdiže jedna isturena kula vazana sa gradom uskim zidom. Plato na kome se prostire tvrđava ima prirodno proširenje na južnoj strani, dok je na severnom kraju jako sužen. Sa zapadne strane, iznad Devotinske reke, uzdizala se nepristupačna litica, pa izgradnja fortifikacija sa te strane nije bila neophodna.