Okolitá krajina patrila v druhej polovici 9. storočia, najmä za panovania Svätopluka do Veľkomoravskej ríše. Svätoplukovi podriadení veľmoži vtedy sídlili a priľahlú krajinu s obyvateľmi spravovali z hradiska v dedine Zemplín. Od 11. storočia bol aj tento kraj súčasťou Uhorského kráľovstva, pričom administratívne patril do Zemplínskej župy, cirkevne do Jágerskej diecézy a v rámci nej do Zemplínskeho arcidiakonátu. Už od 13. storočia sa zachovali písomné správy, v ktorých je zapísaná susedná obec Soľ.
Podľa dokladov Vlastivedného archívu v Prešove sa vznik obce Rudlov datuje od roku 1402. Prvá správa o Rudlove je však z roku 1399, v súvislosti s riešením sporu o tamojší majetok a okolité lesy medzi Abovcami – vlastníkmi panstva Lipovec a šľachticmi z Rozhanoviec. Z obsahu mandáta Palatína vyplýva, že dedina Rudlov jestvovala aj pred rokom 1399. Rudlov sa vyskytuje v písomnostiach z prelomu 14. a 15. storočia pod názvom Rudelfalva. Obec založil šoltýs Rudlo s usadlíkmi podľa zákupného práva okolo polovice 14. storočia. V 15. storočí a v prvej štvrtine 16. storočia patrila šľachticom z Rozhanoviec ako majetková súčasť ich hradného panstva Čičava, neskôr Vranov. Po nich dedinu v roku 1524 zdedili Bátoriovci. V 17. storočí patrila postupne Nádašdiovcom, Ňariovcom, Esterháziovcom, Drugetovcom a ich dedičom. V Rudlove začiatkom druhej polovice 15. storočia hospodárilo okolo 15 domácností, ktoré sa zakrátko takmer všetky odsťahovali. V roku 1493 tam hospodárila len jedna sedliacka domácnosť. Noví obyvatelia sa začali usadzovať v prvej polovici 16. storočia, nepochybne podľa zákupného valašského práva. V roku 1567 boli valašské domácnosti zdanené daňou kráľovi od dvoch port. Dve želiarske domácnosti a domácnosť slobodníka daň neplatili. V roku 1582 sedliakov zdanili od piatich port. Nárast zdanenia svedčí o pribudnutí domácnosti a zväčšení rozsahu pozemkov. V roku 1600 malo sídlo 21 obývaných poddanských domov, dom šoltýsa, kostol a faru pravoslávneho farára. Na prelome 16. a 17. storočia bol Rudlov stredne veľkou dedinou. Začiatkom 17. storočia väčšina valachov Rudlov opustila, iní schudobneli. V roku 1610 vtedajších valachov zdanili len od 0,25 porty. Úpadok valachov spôsobil, že časť z nich sa stala želiarmi. V roku 1623 šoltýskej domácnosti patrilo polovičné šoltýsovstvo. Šesť valašských domácnosti boli želiarske. Žila tam aj domácnosť pravoslávneho farára. V roku 1610 a 1635 zdanili želiarov daňou kráľovi postupne od 0,25 a 0,5 porty. V druhej štvrtine 17. storočia žilo v obci iba želiarske obyvateľstvo.
Nové rusínske obyvateľstvo z prvej polovice 16. storočia sa venovalo najmä ovčiarstvu. Okolo roku 1547 už odovzdávalo zemepánom ovce, jahňatá, kozy a nepochybne aj iné valašské dávky. Postupne obhospodárovali aj polia. Podľa urbára z roku 1585 valašské domácnosti platili zemepánom spoločne ročnú daň 11 zlatých a 50 denárov. Odovzdávali kury a husi, 4 ovce, 4 syry, 2 remenné popruhy a 9 kýt konopí. Odovzdávali tiež vola, avšak spolu s poddanými v Banskom.
Odkupovali od zemepánov 5 gbelov pšenice za 5 zlatých a 75 denárov, ako aj súd vína za 16 zlatých spolu s poddanými z Jastrabia. V 17. storočí zemepáni od nich vyžadovali okrem dane a valašských dávok aj roboty pri oráčke a vystrojenie povozov. Šoltýs v druhej polovici 16. storočia platil zemepánom ročne daň 1 zlatý, miesto chovania lovného krahulca platil 25 denárov. Okrem toho v prvej polovici 17. storočia choval zemepánske žriebätá, alebo chrta a poskytoval povoz.
Tamojší pravoslávny farár v druhej polovici 16. storočia a prvej polovici 17. storočia platil zemepánom ročnú daň 1 zlatý.
Na prelome 17. a 18. storočia bol Rudlov stredne veľkou dedinou. V rokoch 1715 a 1720 v nej bývalo postupne 16 a 18 sedliackych domácností. K dedine patril aj mlyn. V okolitých lesoch sa rozšírila ťažba železnej rudy. V roku 1787 má obec 55 domov a 420 obyvateľov, zaraďuje sa k najväčším na okolí. V tom čase sú jej obyvatelia známi ako dobrí výrobcovia kôs. Pomenovanie obce sa často menilo. V roku 1414 mala názov Reudel, v roku 1474 Rywdel, v roku 1773 Rudlyow, v roku 1808 Rudlow, maďarsky Rudlyó, Ercfalva. Terajší názov obce Rudlov sa zachováva od roku 1920.