Сама фортеця знаходиться на горі вулканічного походження, в той час як місто розташоване на рівнині. Вважається, що саме з горою пов’язано і походження назви міста. Якщо вірити легенді, цю гору створили люди власними руками, в буквальному сенсі «насипали» гору, що коштувало їм величезних мук, звідси, мовляв, і назва – «Мукачево».
Варто цьому вірити чи ні – важко сказати, але точно відомо тільки одне: в ті давні часи людям потрібно було будувати місто навколо потужної фортеці, щоб бути в змозі захиститися від численних ворогів.
Точної дати заснування Паланка ніхто назвати не може, історичні дані говорять тільки про те, що замок існував уже в ІХ столітті. Що стосується назви, саме слово «паланок» означає дубовий частокіл, за допомогою якого обносять рів навколо фортеці і замкової гори. Поки цей частокіл тільки споруджувався, прямо біля нього проживали теслі, ковалі, а також багато інших майстрів, що будували його.