Legenda hovorí, že terajšia dedina je druhou dedinou na tom istom mieste. Ľudia prvého osídlenia vymreli na následky epidémie, dedina zostala opustená, až po čase sa tu znovu usadili ľudia.
Naša dedina leží v údolí medzi horami od Medzilaboriec a Borová s takými názvami : VERCHLAZU, VERCH JASELNIKA, KAMJANA, KULIKOVO, ZAKUŤA,KOTELNICI, ŠTEŇKOVA LUKA, ROZTOKY, HRUNKY, / 537m.n.v./, BRUSY.
Od Malej Poľany, Mikovej- Poľansky vrch / 455 m.n.v. /, Odkiaľ začínajú svoj tok riečky, ktoré sa vlievajú na jednej strane do Laborca a na druhej do Ondavy. Cez dedinu preteká riečka Rokytovka, ktorá sa vlieva do Laborca. Od Roškoviec dedinu oddeľujú polia Kačurka, Lázok, Krajnikova jama, Vrch Molodoj, Malčov vrch, / 513 m.n.v. / od Krásneho Brodu – Laz, Polianky, Popiv kút.Dedinka Rokytovce /Rokytovec/ leží v nadmorskej výške 330 – 335 m /Grécko - kat. chrám/.
Prvá písomná zmienka o našej obci je z roku 1437. Tento rok je aj uvedený vo vlastivednom slovníku obci na Slovensku /2.diel/ vydaný v Bratislave 1977 r. Ďalší je z roku 1599, ktorý je v Maďarskom národnom archíve v Budapešti. Dedina patrila grófstvu Drugetovcov, ktorí od roku 1322 boli vlastníkmi Humenského zámku, od 1323 v Plavči a Ľubovni, od roku 1328 v Jasenove a od r. 1330 v Brekove. Pod vládu Drugetovcov v roku 1572 patrilo 95 dedín, miest a zámkov.
Názov obce pochádza od slova rokyta, čo je drevina, ktorá tu rastla a rastie v hojnom množstve aj dodnes.
Z historických dokumentov sa dozvedáme, že v roku 1715 bolo v Rokytovciach 8 opustených a 10 obývaných domov. V roku 1787 tu bolo 40 domov a žilo tu 275 ľudí, r. 1828 už 43 domov a 323 ľudí.
Okrem hospodárskeho rozvoja sa katolícka cirkev spolu s feudálmi snažila latinizovať pravoslávnych veriacich. Vyriešili to cez zavedenie únie. Prvý pokus mal byť uskutočnený v Krasnobrodskom monastyri na letnice / rusaľa/ v roku 1614. Prichádza episkop Afanasij Krupecky z Premýšľa a pokúša sa preorientovať veriacich. Ľudia kládli odpor, napadli ho, hádzali po ňom kamene. Raneného episkopa zachránil Druget a svojim vojskom nepokoje potlačil.V štátnom archíve v Prešove sa nachádzajú dve knihy – matriky. V prvej sú zachytene roky 1775 – 1841, druha 1828 – 1852 je spoločná s Krásnym Brodom. Sú napísané starosloviensky, latinsky a maďarsky – matriky narodených, zomrelých, sobášiacich sa. V prvej sa spomína meno kňaza Ivana Orgonaša, ktorému Dmitro Michalko bol dlžný za krst 15 grajciarov a Lukač Galan až 27 grajciarov. Zaujímavý je zápis, že 4.VII. 1783 roku mládenec Matvej Čičvakov od dreva zabitý popoludní. Ďalej sa dozvedáme, že najchudobnejším človekom bol Georgij Gobar, ktorý nemal ani vlastný dom. V roku 1796 bolo zapísaných 174 „ valušnych i 54 „ nevalušnych ľudí".
Na pamätniku v obci je na tabuli nápis azbukou: Hrdinskej SA-osloboditeľke vďační občania Rokytoviec za oslobodenie vlasti dali svoje životy Peter Kantuľak nar.21.V.1924 a Michal Druga nar.21.III.1921.
ŠKOLSTVO - do konca XIX. Storočia nie je zápis o škole v Rokytovciach. Funkcie učiteľov vykonávali kantori: „ ďačkove“- Michal Mlej, Michal Suchij, ktorí 2x do týždňa učili deti v domoch Lozjaka a Kovača. Prvá škola bola vybudovaná v roku 1904 – 1906 na mieste, kde teraz stoji kultúrny dom. Prvými učiteľmi boli Kornélia Kollárova a Mariška Suchá. Tretej učiteľky meno nám nie je známe. Ďalší učitelia : Gavrijil Vojtaško, Michal Mihalič, Andrij Gavula, Jeeni Gerberij, Mikolaj Molčanij, Janko Kobulsky ( 1936), Andrej Kusko (1949 – 1972 r. ) Maria Eliašova – Millyova, Olena Kusková, Anna Komanova ( do 1976 r) Anna Bezeková (do 1988 r.). Irena Semanová (1988 – 1994r.) do zrušenia školy. Z rozhodnutia Školskej správy v Humennom bola koncom augusta 1994 r. pozastavená prevádzka školy na 2 roky z dôvodu malého počtu deti. Všetky školopovinné deti začali navštevovať ZŠ na ulici Komenského v Medzilaborciach.
