Leider enthalten schriftliche Quellen keine Informationen über den Bau des Grundsteins der Festung Chotyn und der bis heute bestehenden Zitadelle. Archäologische Untersuchungen ermöglichen es jedoch, über die Entstehung städtischer Siedlungen rund um eine befestigte Burgzitadelle in der Antike zu sprechen. Ein slawisches Dorf auf dem hohen Felsvorsprung des Dnjestr war möglicherweise bereits im 8. und 9. Jahrhundert durch einfache Holzbefestigungen an der Bodenseite geschützt. Im 10. und 11. Jahrhundert umfasste die Siedlung ein deutlich größeres Gebiet (etwa 20 Hektar) und erstreckte sich, wie Funde von Hausresten und Stuckarbeiten belegen, auch auf die umliegenden Hügel.

Die Lage der Zitadelle in einer Tiefebene, die an drei Seiten von Hügeln umgeben ist, deutet darauf hin, dass die älteste Burg lange vor dem Aufkommen von Artillerie und Steinschleudern erbaut wurde.

Die ersten zuverlässigen Befestigungsanlagen in Form eines Erdwalles mit Holzzäunen und eines über den Felsvorsprung gegrabenen Grabens entstanden vermutlich im 10. und 11. Jahrhundert. Man nimmt an, dass die ersten Steinbefestigungen der Festung Chotyn in den 40er und 50er Jahren des 13. Jahrhunderts errichtet wurden, als Danylo Romanowitsch, Fürst von Halizki, die alten Befestigungen verstärkte und neue zum Schutz vor den mongolisch-tatarischen Invasionen erbauen ließ.

Einer anderen Ansicht zufolge geschah dies nach 1259, als Danylo und Wassylko Romanowitsch auf Geheiß der Mongolen und Tataren gezwungen waren, alle Verteidigungsanlagen des Fürstentums, einschließlich der hölzernen Befestigungen von Chotyn, zu zerstören.

An deren Stelle wurden später Steinbefestigungen errichtet. Die ersten Steinmauern könnten sogar noch früher, im 12. oder in der ersten Hälfte des 13. Jahrhunderts, errichtet worden sein, als die militärischen Konflikte zwischen dem Fürstentum Galizien-Wolhynien und dem Königreich Ungarn andauerten. Das Gelände der alten Steinburg befand sich im nördlichen Teil des heutigen Festungshofs.

Die erste Festung war klein, mit einer Fläche von nicht mehr als zwei Hektar, umgeben von einer Mauer und einem annähernd dreieckigen, sechs Meter breiten Graben. Nur die Mauerreste, verborgen in der Stärke der östlichen Kurtine, sind erhalten geblieben. Vermutlich war der Turm an der Stelle des heutigen viereckigen Nordturms das wichtigste Verteidigungsbauwerk. Es könnte sich um einen Turm gehandelt haben, der unmittelbar in das Mauersystem integriert war, oder um einen separaten Bergfried, an den später etwa dreißig Meter lange Mauern angebaut wurden, wodurch ein quadratischer Innenhof entstand.

Mitte des 14. Jahrhunderts erfolgte eine teilweise Rekonstruktion und Verstärkung der Befestigungsanlagen von Chotyn: Eine etwa einen halben Meter dicke Mauer aus dieser Zeit, die in einer Tiefe von 3,5 Metern unter der heutigen Oberfläche gefunden wurde, verlief entlang der Nordgrenze des Kommandantenpalastes bis zur östlichen Kurtine und diente als südliche Verteidigungsmauer. Diese Maßnahmen wurden in der Anfangsphase der Eroberung galizischer Gebiete durch die moldauischen Woiwoden im Oberlauf der Flüsse Suceava, Siret und Prut durchgeführt.

Mit der Eingliederung Chotyns in das Fürstentum Moldau in der zweiten Hälfte des 14. Jahrhunderts erlangte die Stadt als Handels- und Zollstation an der Nordgrenze Moldaus bedeutende militärische und politische Wichtigkeit. Der moldauische König Stephan III., allgemein bekannt als Stephan der Große (1457–1504), begann aktiv mit dem Ausbau des strategischen Verteidigungssystems des Fürstentums Moldau, das aus neun Festungen, darunter auch Chotyn, bestand. Dies war vermutlich auf die Entwicklung der Artillerie ab Mitte des 15. Jahrhunderts zurückzuführen.

In den 1460er- und frühen 1470er-Jahren des 15. Jahrhunderts wurde die Burg Chotyn vollständig umgebaut und nach Süden mehr als verdoppelt, sodass sie nun eine Größe von etwa 110 × 55 m erreichte (einschließlich des Nord-Südwest-Turms Kowalska). Dicke (bis zu 5 m) und hohe (bis zu 40 m) Mauern und Türme wurden zum Schutz vor Kanonenfeuer errichtet. Sie waren mit roten Ziegelornamenten verziert – Reihen von Darstellungen Babylons (vermutlich ein Symbol architektonischer Meisterschaft) und Golgathas (des Felsens, an dem Christus gekreuzigt wurde – einer der wichtigsten christlichen Wallfahrtsorte). Die so verzierten Mauern gewannen an Stärke, zusätzlich geschützt durch die Kraft des orthodoxen Glaubens. Anfang des 18. Jahrhunderts beschloss die Hohe Pforte des Osmanischen Reiches, die Verteidigungsfähigkeit der Festung zu verbessern. Laut historischen und literarischen Quellen rückten im Juli 1713 „mehr als 100.000 Mann, 200 große und kleine Geschütze, Pferde, Ausrüstung und Werkzeuge zur Verstärkung der Festung in Richtung Chotyn vor, da es notwendig war, sowohl die Festung als auch die Stadt Chotyn am Dnjestr zu stärken“. Anschließend wurden die Lücken zugemauert, der südwestliche Turm mit deutlich dickeren Mauern als zuvor wiederaufgebaut, eine neue Wehrmauer und ein Torturm errichtet und weiter südlich verlegt. Die Erweiterung der Burg in dieser Zeit wird unter anderem durch die Details osmanischer Architektur belegt, die beim Entwurf der neuen Befestigungsanlagen Verwendung fanden.

Zeitgleich mit dem Wiederaufbau der Zitadelle errichteten die Türken um sie herum stärkere Befestigungsanlagen – die Neue Festung. Die Burg verlor ihre Bedeutung als eigenständiges Verteidigungsbauwerk und wurde Teil eines neuen Befestigungssystems. Sie umfasste den östlichen Teil des Hofes des neu entstandenen Verteidigungskomplexes und diente fortan als Arsenal. Der Eingang zur Zitadelle benötigte nun keinen zusätzlichen Schutz mehr und wurde daher in die östliche Seitenwand des unteren Geschosses des neuen Übertorturms integriert, wodurch die Munition schnell abtransportiert werden konnte. Die Öffnungen zwischen den Pfeilern der alten Brücke aus dem 15. Jahrhundert wurden mit Steinen verschlossen, wodurch dieser Bereich in das allgemeine System der äußeren Befestigungsanlagen einbezogen wurde.

Von jener Zeit bis heute hat die Festung Chotyn infolge zahlreicher Kriege, Schlachten auf ihrem Gebiet und wechselnder Herrscher bedeutende architektonische Veränderungen erfahren. Die Majestät und Macht der Burg, die sich über den Dnjestr erhebt, sind jedoch unverändert geblieben.