Obec je doložená z roku 1382 ako Elsewa, neskôr ako Olsua (1391), Felsew Elswa (1394), Ilswa (1410), Felsew Olswa (1474), Wissní Olssawy (1808), Vyšná Oľšava (1920); po maďarsky Felsöolsva.
Obec patrila panstvu Čičava, v roku 1493 panstvu Makovica, v 18. storočí Dessewffyovcom a iným. V roku 1493 mala z 11 usadlostí 8 opustených, v roku 1715 mala 34 opustených a 22 obývaných domácností, v roku 1787 mala obec 64 domov a 480 obyvateľov, v roku 1828 mala 56 domov a 449 obyvateľov. Zaoberali sa poľnohospodárstvom a drevorubačstvom. Začiatkom 20. storočia vlastnila tu majetky rodina Grustyinszkovcov.
Za I. ČSR sa zamestnanie obyvateľov nezmenilo. JRD založené v roku 1949 sa v roku 1957 rozpadlo, znovu bolo založené v roku 1960. Časť obyvateľov pracovala v priemyselných podnikoch v Stropkove.
Zdroj: Vlastivedný slovník obcí na Slovensku, 3. časť