Archeologické nálezy z predhistorického obdobia a starších úsekov historického obdobia nie sú známe. Najstaršia zmienka o Medzilaborciach je v donácii uhorského kráľa Ľudovíta Veľkého zo 7. januára 1347, v ktorej sa územie uvádza medzi 92 obcami panstva Drugethovcov ako Mezobrod.  Medzilaborce sa ako mesto prvý krát spomínajú roku 1543 (Kis Laborcz). Jeho rast a rozvoj je podrobne zaznamenaný v mestskej kronike, avšak mestu nikdy neboli udelené mestské privilégia. Medzilaborce ani žiadne zo sídiel terajšieho okresu v období do 16.storočia nemali väčší význam, spojený s právom usporiaduvať trhy a jarmoky. V roku 1612 sa v Medzilaborciach zriadila píla a dva mlyny. V roku 1631 sa zriadili prvé potravinárske obchody a hostince. Vlastníkmi Medzilaboriec boli po vymretí rodu Drugethovcov po meči od roku 1684 Csákyovci.

V r.1860 sa Medzilaborce stávajú mestom a jedným z 21 administratívnych celkov v Zemplínskej župe. V meste v roku 1869 prebehlo sčítanie obyvateľstva. Podľa neho boli v meste viaceré priezviská. Podľa týchto informácií si vieme predstaviť úroveň života v Medzilaborciach. V r.1873 boli Medzilaborce napojené na železničnú dopravu. V r. 1881 cez Medzilaborce cestoval císar František Jozef I., ktorý sa vracal z Halíča. V 19. storočí boli vlastníkmi majetkov v Medzilaborciach Andrássyovci. V roku 1885 mal v Medzilaborciach statok gróf Andrássy, ktorý mala v prenajme vdova Schonfeldová. Pri ničivom požiari v r. 1900 zhoreli takmer všetky domy okrem greckokatolického chrámu. Na začiatku 20. storočia bolo mesto i celá oblasť takmer bez priemyslu a obchodu so slabým školstvom. Mestečko Medzilaborce stáva okresným centrom v roku 1910.

Na vojnu sa Rakúsko-Uhorsko chystalo veľkými zemplínskymi vojenskými manévrami v roku 1911. Viedol ho následník trónu František Ferdinand a zastavil sa i v Medzilaborciach. Práve jeho smrť o tri roky neskôr bola zámienkou na svetovú vojnu. 

Vojenské manévre naznačili, kde sa v prípade vojny bude bojovať.  Počas I. svetovej vojny východný front zasiahol aj túto oblasť,  mesto bolo viackrát zničene. Prvá svetová vojna priniesla obyvateľstvu Medzilaboriec a okolia nesmierne útrapy. Počas bojov sa z Medzilaboriec a okolia takmer dve tretiny obyvateľstva presťahovali až k Miškolcu a Debrecenu. V rokoch 1914-1915 boli Medzilaborce značne poškodené a boli sídlom štábu veliteľa ruskej armády generála Brusilova. Cez Medzilaborce ako vojak 91. pluku prechádzal v roku 1915 i spisovateľ Jaroslav Hašek. Mesto spomína i vo svojom diele "Osudy dobrého vojáka Švejka za světové války".  V období 1.ČSR v kraji vládla nezamestnanosť, silné vysťahovalectvo a nízka životná úroveň. Jedným z mála podnikov bola píla na drevo. Na Základnej škole v Medzilaborciach v tridsiatych rokoch končili mladí, ktorí ešte nevedeli aká pohroma ich o niekoľko rokov čaká.

Počas II. svetovej vojny bolo mesto znova viackrát zničene. 23. februára 1945 bolo v Medzilaborciach založené Štátne ruské gymnázium. Z hľadiska historického je dôležitý fakt, že po oslobodení v roku 1945 sa Medzilaborce stali prvým okresným sídlom na území ČSR. Túto funkciu plnilo mesto do roku 1960. Od roku 1960 patrilo do okresu Humenné. Po oslobodení vznikla sieť škôl, začal sa budovať priemysel a poľnohospodárstvo. V r.1955 v Medzilaborciach bola zriadená Nemocnica s poliklinikou.
Medzilaborce a jeho okolie boli bez priemyslu, a preto vtedajšie vedenie rozhodlo, že v Medzilaborciach bude postavený strojársky závod. 1. mája 1958 bol položený základný kameň závodu – Transporta. V roku 1971 po rekonštrukcii starého mlyna sa začala prevádzka nového závodu Jablonecké sklárne (neskôr Lusk). Okresným mestom je znovu od roku 1996.