Колись дуже давно в долині річки Уж поселилась турецька царівна. Це була жорстока чародійка, і народ прозвав її Поганою Дівою.
Задумала Погана Діва на крутій горі над Ужем серед дрімучих лісів побудувати для себе неприступну фортецю. Яничари згоняли людей піднімати на гору каміння і будувати твердиню. Для міцності вапно Погана Діва наказала гасити молоком та білками яєць. Та навіть цього їй показалося замало? і вона наказала примішувати до вапна материнське молоко. Почали помирати маленькі діти. По всій долині стояв плач, та Погана Діва лише посміхалася.
Та навіть цього Діві не вистачило. Задумала вона додавати до вапна ще й людську кров.
Не стало народу легше навіть тоді, коли замок було вже збудовано. Вояки Поганої Діви рискали по селах, сама вона з башти замка стежила за перехожими. Хто йшов попри замок та не кланявся їй низенько, тому вона веліла голову рубати. Стали люди це місце обходити.
Жив в той час в недалекому селі Ореховіце робітник Іванко. Він якось сказав своєму хазяїнові, що визволить народ від Поганої Діви, як тільки стане царем.
- Коли це залізо заквітне, тоді ти будеш царем, - відповів хазяїн, встромивши в землю істик (паличку з наконечником для чищення плугу).
Раптом на його очах істик перетворився в зелений куст з пишними трояндами. Відпустив хазяїн Іванка, пішов той в Ужгород, де якраз вибирали царя. Хтось запропонував зібравшимся аристократам, що ніяк не могли розібратися поміж собою, підкинути в повітря золоту царську корону. На чию голову вона опуститьс, той царем і буде.
Підкинули. І впав цей вінець на голову Іванка.
- Не бути мужику царем, - сказали аристократи. І знов підкинули корону. З тим же результатом. І в третій раз корона опустилася все на ту ж голову... що робити – став Іванко царем. Зібрав він велике військо, а також велів зігнати великі стада худоби. Пішло це стадо по направленню замку. Було вже темно, Іванко наказав прив‘язати до кожної тварини дзвіночок, а поміж роги поставити в‘язанку сіна та підпалити її.
- Коли все стадо з ревінням посунуло на фортецю, то Погана Діва прокинулася від страшного галасу. Перестрашилась царівна, вскочила на свого чарівного коня і помчала в бік Ужгорода. Та Іванко помітив утікачку – і почалася погоня. Проминули вершники Ужгород, вже попереду – річка Латориця. Дорога йшла густим дубовим лісом, і Погана Діва зачіпилася своїм розкішним волоссям за густі гілки та повисла на них, а кінь її поскакав далі.
- Як вже просила царівна Іванка не губити її, пропонувала своє серце... та убив Іванко жорстоку чародійку. Тіло її було спалено, а над попелом насипали курган. І зараз він стоїть під замком в долині коло поля.
За іншими даними, замок названий Невицьким тому, що повинен був захищати “невіст” (дівчат) міста. Назва поступово трансформувалась в Невицьке. В 14 ст. магнат Другет перебудував твердиню, замінив дерев‘яні укріплення кам‘яними. Кажуть, Погана Діва була його спадкоємицею. Такий персонаж дійно існував, та була та чародійка не бусурманкою, а угорською графинею. Вона дійсно наказувала селянам в вапно яйця з молоком примішувати. Хто не слухався – того піддавали всіляким карам. Жалоби на її сваволю доходили до тогочасного короля Матьяша, він, обурений, навіть зібрав військо, щоби силоміць доставити графиню до двору для судового процесу. Та до того часу Невицький замок став настільки міцним, що міг витримати не одну осаду. Король пішов на хитрість – саме ту, з худобою, про яку народ і розказує в легенді про Іванка.
В 15 ст. замок був частково зруйнований військами князя Д‘єрдя Ракоці ІІ. З того часу споруда стояла пусткою і вважалася нечистим місцем.

Нарешті, за третьою легендою, володар Невицького замку Упор відбив у мукачівського герцога Горо наречену — і щоб втамувати злість суперника, пообіцяв йому: якщо матиме доньку, віддасть її в 16 років в дружини герцогу. Так і сталося — і за 17 років приїхав у Невицьке старий Горо. Юна дівчина, дізнавшись, якого нареченого їй обрав батько, у розпачі кинулася з замкової башти вниз. Сама природа постала проти неприродного вчинку — і блискавка влучила в вежу, зруйнувавши твердиню.