Historia thumb|left|Pomnik uczestników słowackiego powstania narodowego Z badań archeologicznych wynika, że okolice Vranova były zamieszkane już w VII wieku. Kościół parafialny istniał już w 1314. Pierwsze wzmianki o mieście pochodzą z lat 1333–1337. Jeszcze w I połowie XIV w. Vranov stał się osadą targową, wyposażoną przez króla Węgier Ludwika w prawo wolnego handlu. Data nadania Vranovowi praw miejskich nie jest znana, jednak już w liście króla Zygmunta z 1410 r. jest wzmiankowany jako miasto. W XV wieku Vranov przeobraził się w ośrodek rzemiosła i handlu, rozrastający się w miarę wzrostu znaczenia szlaku handlowego z Polski na Węgry przez Przełęcz Dukielską. W 1461 r. został obdarzony przywilejami przez króla Macieja Korwina. Posiadał prawo składu towarów oraz organizacji dorocznych jarmarków.
Podczas wojen w XV i XVI wieku Vranov został mocno dotknięty zniszczeniami, jednak w 1607 r. uzyskał kolejne przywileje od cesarza Rudolf II Habsburga. Od 1523 r. należał do magnackiego rodu Batorych, od 1617 do rodu Drugethów, od 1684 do rodu Bárkoczy. Hrabina Mária Esterházy założyła tu klasztor paulinów, zniesiony w 1786 r. w wyniku reform sekularyzacyjnych cesarza Józefa II Habsburga.