В конце XI века Хотин становится частью Теребовлянского княжества, затем переходит под власть галицких князей, ас 1199 года крепость на Днестре вошла в состав Галицко-Волынского княжества. Спустя два десятилетия до Восточной Европы докатывается гул копыт миллионов коней, несущих на себе не знающих преград монголо-татарских всадников. Князь Даниил Галицкий в надежде остановить войска хана Батыя решает серьезно укрепить свои замки, в том числе и Хотинский. Деревянные укрепления заменены каменными, глубокие рвы и стена семиметровой высоты окружили замок. Внутри крепости была построена Красная, или Николаевская, церковь, сохранившаяся до наших дней.

После монголо-татарского нашествия Галицко-Волынское государство значительно ослабло, соседи, которые раньше и не помышляли о том, чтобы напасть на мощное княжество, получили возможность без особых усилий прибрать к рукам буковинские земли. Во второй половине XIV века Хотин оказывается во власти Венгерского королевства, а затем переходит под власть молдавского господбря Стефана III Великого. В крепости разворачивается строительство, Стефан III, понимая огромное стратегические значение Хотинского замка, лично руководил постройкой новых стен (высотой до 40 и шириной более 6 метров), трех башен и двух дворцов с обширной системой подземных помещений и ходов. Для того чтобы осажденный гарнизон не остался без воды, был сооружен колодец, уходящий на глубину более 70 метров.

В 1476 году хотинская твердыня прошла первое серьезное боевое крещение, выдержав осаду войск турецкого султана Мухаммеда II. Однако противостоять натиску Турции Молдавское княжество все-таки не сумело и в итоге на рубеже XV и XVI столетий попало под вассальную зависимость от турецкого султана. На несколько десятилетий Хотинская крепость становится собственностью Турции, на ее территории размещается гарнизон турецких войск, строится несколько мечетей. В это время Хотин приобретает значение не только как стратегически важный замок, но и как большой торговый центр.

Речь Посполита очень ревниво относилась к турецкому форпосту, ведь Хотин был расположен недалеко от польской границы. И потому поляки неоднократно предпринимали попытки овладеть Хотинской крепостью. До поры до времени турецкому гарнизону удавалось отбивать атаки польских войск, однако в 1538 году хорошо укрепленная крепость все-таки не выдержала натиска армии под командованием Яна Тарновского. Чтобы взять Хотин, нападавшие незаметно сделали несколько подкопов, заложили в них мощные пороховые заряды и взорвали большую часть стены и три башни.

Однако и полякам не удалось надолго закрепиться в Хотине. Крепость снова переходит из рук в руки. В 1563 году замок захватил князь Дмитрий Вишневецкий, стоявший во главе отряда из полусотни запорожских казаков. Спустя несколько десятилетий в цитадели обосновываются молдавские князья Семен (отец Петра Могилы) и Иеремия Могилы, спасавшиеся на берегах Днестра от преследования их противника – валашского господаря. А в 1620 году Хотин опять переходит под власть турецкого султана. После этого между Речью Посполитой и Турцией вновь вспыхнула война, получившая название Хотинской. Для Польши военная кампания началась с катастрофического поражения под молдавским городком Цецора. Коронный гетман Станислав Жолкиевский безрассудно решил покинуть стены Хотина и отправился навстречу врагу. За что и поплатился. Десять тысяч польских шляхтичей и казаков не имели никаких шансов в битве против 40-тысячной турецко-татарской армии. Голова Жолкиевского, насаженная на пику, была отправлена в подарок султану Осману II. Многие казаки были захвачены в плен, и среди них молодой Богдан Хмельницкий.