Pierwsza wzmianka o osadzie pochodzi z 1543, gdy włączono ją do włości węgierskiej magnackiej rodziny Drugethów. Prawa miejskie zostały nadane w 1964, kiedy to również przyłączono do Medzilaborec kilka wsi. Region, w którym leżą Medzilaborce – Górny Zemplin – jest uważany za najuboższą część Słowacji. Oficjalny wskaźnik bezrobocia w mieście wynosi 20,63%. Wśród mieszkańców miasta przeważają Rusini, mieszkają tu także Słowacy i Cyganie. Ludność jest wyznania greckokatolickiego, rzymskokatolickiego i prawosławnego. Miasto stanowi ośrodek narodowego ruchu rusińskiego, odbywają się tu coroczne festiwale kultury rusińskiej i ukraińskiej.
Miasto składa się z domków jednorodzinnych i osiedli bloków mieszkalnych, jest tu również kilka niewielkich zakładów przemysłowych. Medzilaborce są znane przede wszystkim z galerii sztuki nowoczesnej, mieszczącej się w miejscowym domu kultury, w której prezentowane są prace Andy’ego Warhola oraz jego braci Paula i Jamesa. Rodzina Warholów przed emigracją do USA mieszkała we wsi Miková (17 km na zachód od miasta). Muzeum zostało otwarte staraniem miejscowej społeczności rusińskiej w 1991. Poza tym w mieście warte obejrzenia są dwie cerkwie: prawosławna (pw. Świętego Ducha, wzniesiona w 1949 w stylu staroruskim) i greckokatolicka (św.