A vár maradványai a 334 méter magas Várhegy nevű hegygerincen helyezkednek el. A források a várat Patak-, Nagypatak-, Sátorhegy- és Újhely váraként is említik: Pataknak nevezték, mivel a pataki erdőispánság, majd a pataki uradalom tulajdonába tartozott, Újhelynek pedig azért, mert Sátoraljaújhely külterületén helyezkedett el.

Anonymus Gesta Hungarorumának 15. fejezetében azt olvashatjuk, hogy Árpád fejedelem a Sátorhalomtól a Tolcsva folyóig terjedő “egész földet”, egy bizonyos Ketel vitéznek adományozta, melyet aztán annak utódaitól I. András király szerzett meg birtokcserével. Az újhelyi Sátorhegytől nagyjából a mai Olaszliszkáig terjedő terület a XIII. század elején már régóta zárt királyi birtoktömböt alkotott, mely fontos helyszíne volt a királyi vadászatoknak, és összefüggött a királyi udvar bizonyos alkalmankénti itt tartózkodásával is. A vár a tatárjárást követően épült, első ismert említése 1261-ből való, István hercegnek (később V. István királ) a pataki ispánságba újonnan érkezett sátorelői vendégnépek, azaz hospesek számára széles körű előjogokat biztosító városprivilégiumában. Funkciója szerint az Ungvár irányába futó fontos utat őrizte és István herceg családjának volt a szállása. István herceg és apja, IV. Béla között konfliktus alakult ki, ezért 1264-ben István herceg nővére, Anna hercegnő ostromolta meg Henrik nádor vezetése alatt. A vár hamar elesett és a herceg feleségét, lányait és a 2 éves László herceget (később IV. (Kun) László király, kinek történetéről már olvashattatok az oldalon a körösszegi vár kapcsán) a Turóc megyében lévő Turul, majd később Zniónak nevezett várba vitték fogolyként.

1281-ben IV. László és a hivataláról az év tavaszán leváltott nádora, Aba nembeli Finta – Aba Amadé testvére – között komolyabb belháború alakult ki. 1281 nyarán a Gömör megyei Gede és az Abák fontos hatalmi központjának számító abúji Szalánc várát ostromolták IV. László seregei. IV. László 1282 júliusában és augusztusában több oklevelet is keltezett az ekkor Patak várának hívott erősség alatt. Valószínűleg azért tartózkodott itt hosszabb ideig, mert ekkor került sor Patak várának ostromára. Magáról az ostromról egy 1282-ben kelt királyi adománylevél tesz konkrét utalást. A források nem említik, hogy a várat ekkor kitől kellett visszafoglalnia az uralkodónak. Nem kizárt, hogy Patakot maga Finta védte, de az sem, hogy az Abák köréhez tartozó korábbi beregi (1273) és pataki (1273-1282) ispán, akkor erdélyi vajda Tekes fia István tartotta birtokban a várat. Bárhogyan volt, a harc a király győzelmével végződhetett.

1285-ben a második tatárjárás alatt a közeli Patakot elpusztították a mongolok, de a vár esetleges ostromáról nincs adat.

IV. László meggyilkolása után híve, Baksa nembeli Simon fia György várnagy 1291-ben átadta a várat III. András királynak. Az új király IV. Lászlóhoz hasonlóan megerősítette az újhelyi hospesek V. Istvántól kapott 1261-es kiváltságait egy oklevélben, és ebben nevezik először Sátoraljaújhelynek a települést.

Az Árpád-ház kihalása (1301) után a Baksák I. Károly oldalára álltak. 1312-ben a Patak városát az Amadé-fiak kifosztják, de seregüket Petenye fia Péter, valamint Baksa nembeli László és Dancs szétverték. Az oklevelek szerint a Baksák 1319-ig birtokolták Újhely várát és uradalmát. Babonics János királynéi tárnokmester és várnagy 1334-ben kelt végrendeletében nevezik először Újhely várának az erősséget.

1390-ben Luxemburgi Zsigmond király adományozó oklevelet állított ki Perényi Miklósnak Patak és Újhely városairól és a közelükben lévő várról, de csak 1392-ben iktatták be a birtokokba. Mivel fia 1428 nyarán Galambóc ostrománál életét vesztette, ezért Patak, Újhely és a vár visszaszállt a királyra. Ő 1429 júliusában Újhely várát és mezővárosát Pálóczi Péter fiainak, Györgynek, Máténak és Imrének adományozta.

Az utolsó Pálóczi birtokos, Antal, Zemplén vármegye főispánjaként 1526. augusztus 29-én a mohácsi csatában halt hősi halált, végrendeletében Katalin húgának fiait tette meg örököseivé. Ez azonban nem valósult meg, mert Perényi Péter a Pálócziakkal való nőági rokonságra hivatkozva rátette kezét a pataki uradalomra. Perényi – aki részt vett a mohácsi ütközetben, ő vezette a magyar sereg balszárnyát, amely az anatóliai seregtesttel szemben a korabeli török források említése szerint nagy vitézséggel harcolt - koronaőrként részt vett Szapolyai János fehérvári koronázásán, mely után a koronát a füzéri várában helyezte biztonságba. Perényi Szapolyai János királytól megkapta (Sáros)Patak és Újhely birtokokat és az erdélyi vajda címet, de 1527-ben pártot váltott (Ferdinánd büntetlenséget ígérve neki a táborába hívta őt, egy későbbi levelében pedig arra kérte a főurat, hogy addig ne valljon színt, míg ő haddal nem jön az országba) és átadta a koronát Habsburg Ferdinándnak. I. Ferdinánd megerősítette Perényit a Szapolyai Jánostól kapott birtokaiban, de ezeket a birtokokat korábban már Thurzó Elek kincstartónak is megígérte. végül megkérte őt, hogy azokat engedje át Perényinek.

1528 elején János király Debrecenből megindította hadait Felső-Magyarország visszafoglalására. Miután Tokaj, majd Sárospatak is a kezére került, megindult az Athinai Simon által védett újhelyi vár alá. A várat végül feladta Simon és átpártolt János oldalára, aki március 1-én Terebesen át tovább indult Kassa felé, ahol március 8-án a Kassa melletti Szinánál súlyos vereséget szenvedett Ferdinánd hadvezérétől, Johann Katzianertől. 1529 elején Ferdinánd Katzianert küldte jelentős létszámú német zsoldossereggel, hogy foglalja vissza Felső-Magyarországot és a Tiszántúlt. A sereghez Perényi Péter és Török Bálint is csatlakozott. Március elején Regéc és Boldogkő már Katzianer kezén volt, és a hónap közepén hozzáfogott Újhely ostromához, ami hetekig elhúzódott. A sereg nem volt a várostromhoz szükséges komolyabb tűzerővel felszerelve, így Katzianer a vár aláaknázásával próbálkozott. A várat április közepén a várbeliekkel kötött megegyezés útján sikerült elfoglalnia.

1533-ban lehettek a várban kisebb építkezések, amire egy 1533-as évszámmal ellátott kapuív utalhat.

Perényi 1534-ben – kétszeri török fogság után – elkezdte Sárospatak várának felépítését. 1537-re felépült az új rezidencia, az eredetileg ötszintes, lőréses védőfolyosóval ellátott ágyútorony és reprezentatív lakótorony sajátos kombinációjaként megjelenő, későbbi nevén ún. Vörös torony. Erről szintén olvashattatok már az oldalon. Ezért viszont jelentősen csökkent Újhely hadászati jelentősége. Közben – korábbi szokásához híven – ide-oda pártolt Ferdinánd és János király között adományokért cserébe, de végül János 1537 decemberében újraadományozta a korábbi Pálóczi birtokokat, így Újhely és Dédes várakat, Sárospatak, Céke és Helmec várait, Újhely és Sárospatak mezővárosokat, valamint Sajószentpétert és Pétervásárát Perényinek. 1540 őszén ismét Ferdinánd pártjára állt, miután megkapta a kancellári méltóságot és 1542 márciusa és októbere között a Dunától keletre és északra fekvő területek főkapitánya lett. Ferdinándnál azonban végérvényesen betelt a pohár: 1542 októberében vasra verték és fogságba vetették. Innen csak 1548-ban, közvetlenül a halála előtt szabadult.

1538 őszén a leleszi konvent jelentése szerint Újhely már romos volt, és a későbbi oklevelek is már leromboltként említik a várat. Végső történetét nem ismerjük: elképzelhető, hogy a Ferdinánd-párti seregek ostromában pusztult el, de lehet, hogy maga Perényi romboltatta le, miután felépült Sárospatak vára.
Régészeti feltárása 2007-ben indult meg és azóta is folyamatos.