История прежде русского, а теперь - польского города Пшемысля (Перемышля) уходит корнями в рубеж IX-X веков, когда тут существовало поселение мадьяр, не решившихся на переход Карпат вслед за князем Арпадом, но в 981 году Карпаты завоевал великий князь киевский Владимир Святой, перемышльские мадьяры, не желая ему подчиняться, ушли в Венгрию, а Перемышль, как столица нового уголка Древнерусского государства, получившего название Червонной Руси, получил мощные деревянные укрепления, вошедшие в историю как Перемышльский кремль.
Завоевав Перемышль в 981 году, князь Владимир сразу принялся за активное строительство укреплений на Замковой горе, что на правом берегу Саны, где был насыпан мощный вал и поставлен частокол, но они не спасли Перемышль в 1018 году, когда город взял штурмом польский король Болеслав I Храбрый, который после неудачи экспедиции на Русь, охваченную междоусобной войной 1015-1019 годов, решил добиться здесь хоть какого-то успеха. В первый раз польским городом Перемышль пробыл недолго, уже в 1031 году его взял штурмом Ярослав Мудрый, но поляки за это время успели отметиться в Перемышльском кремле, построив там первую в Перемышле католическую церковь-ротонду и дворец, простоявший до XVII века. После освобождения Перемышля местный кремль был значительно усилен, вал получил срубную сердцевину, аналогично были построены его стены и башни, в правление князя Володаря Ростиславича (1085-1092) здесь был построен каменный собор святого Иоанна, ставший усыпальницей перемышльских князей. На протяжении нескольких сотен лет Перемышльский кремль был самой мощной крепостью Червонной Руси, перед которой неизменно пасовали все враги.
Монгольские завоеватели пощадили Перемышль, в 1240 году после завоевания Южной Руси они перешли Карпаты значительно севернее, оставив город в покое, но после монгольского завоевания Русь сильно ослабла и на Червонную Русь предъявили претензии Польша и Венгрия, но пока были живы князья Даниил Галицкий и его потомки, взять Перемышль было невозможно, но после того, как в 1323 году местная династия, ведшая свою родословную от Рюриковичей, пресеклась, участь Перемышля была предрешена, однако он продержался без посторонней помощи до 1345 года, когда его взяли поляки, сделав Перемышль первым городом так называемой "Польской Руси". Прежний кремль, порядком порушенный во время последней осады, уже не удовлетворял поляков и на его месте они построили каменный готический замок, фрагменты которого сохранились до настоящего времени.