La unua skriba mencio devenis el 904. La tataroj detruis la komunumon en 1241. Poste la komunumo refondiĝis kune kun abatejo iomete for de la ruinoj, ĉar dum la historio Bodrog ofte inundis. Ĝi ricevis rangon urbo en 1261, havanta fortikaĵon. La bienoj apartenis ekde 1351 al litovaprinco, kiu setligis rutenojn. La fortikaĵo detruiĝis en 1558 laŭ ordono de Habsburgoj, la sendefenda urbo suferis en 1566 rabadon kaj detruadon de turkoj. Hajdukoj de Stefano Bocskay vivadis en la urbo ekde 1605. En 1697 en la tuta regiono - ankaŭ ĉi tie - okazis ribelo kontraŭ Habsburgoj. En la 18-a jarcento alvenis judoj, kiuj precipe komercadis, dume la urbo iĝis departementejo de Zemplén, la departementa domo konstruiĝis en 1768. En 1739pesto, en 1831ĥolero, en 1834 tertremo, en 1845inundo okazis. La fervojo konstruiĝis el Miskolc en 1871, post unu jaro al Ungvár.
Urbodomo de Sátoraljaújhely
Malliberejo konstruiĝis en 1905, ankaŭ nun funkcianta, en 1944 okazis granda ribelo kaj rifuĝo, fine estis 60 da mortintoj. La ĉeĥoj okupis la urbon en 1919, iom poste la tiama hungara ruĝa armeo reokupis la regionon, poste retiriĝis, kredante al Antant, kiu promesis kompense retiriĝon de rumanoj. Fine en 1920 la naskiĝanta Ĉeĥoslovakio pretendis fervojan linion el Rumanio. Tial Sátoraljaújhely estis distranĉita, la norda parto kun la fervojo apartenas al la nuna Slovakio, - havanta la nomon Slovenské Nové Mesto - , la suda parto kun la urbocentro restis hungara, kiu ĝis 1984 havis titolon distriktrajta urbo. Ambaŭ partoj iĝis limpasejoj. Ekde 2008 Hungario kaj Slovakio apartenas al interna zono de Schengen, la limoj inter du urbopartoj malaperis.
Inter 1938-1945 la du urbopartoj unuiĝis, en 1944 la judoj estis deportitaj.
