Infelizmente, as fontes escritas não contêm informação sobre como foi a construção da primeira pedra da Fortaleza de Khotyn e da cidadela existente até aos dias de hoje. Mas os estudos arqueológicos oferecem uma oportunidade para falar sobre o surgimento de núcleos urbanos em torno de um castelo-cidadela fortificado na Antiguidade. A aldeia eslava no alto do promontório rochoso do Dniester já estaria protegida por simples fortificações de madeira do lado do solo, existentes nos séculos VIII-IX. Nos séculos X-XI, o povoado ocupava uma área muito maior (cerca de 20 hectares), alargando-se , a julgar pelos achados de restos de casas e estuques, nas colinas vizinhas. A localização da cidadela numa planície, rodeada de colinas em três lados, indica que o castelo mais antigo foi construído muito antes do aparecimento não só da artilharia, mas também dos engenhos de lançamento de pedras.

As primeiras fortificações fiáveis, sob a forma de uma muralha de terra com vedações de madeira e um fosso escavado sobre o promontório rochoso, surgiram provavelmente na fronteira entre os séculos X e XI. Acredita-se que as primeiras fortificações de pedra da fortaleza de Khotyn possam ter surgido nas décadas de 40 e 50 do século XIII, quando Danylo Romanovych, príncipe de Halytskyi, fortificou as antigas e construiu novas fortalezas para as proteger da invasão mongol-tártara. Outra opinião é a de que tal aconteceu depois de 1259, quando, a pedido dos mongóis-tártaros, Danylo e Vasylko Romanovych foram obrigados a destruir todas as estruturas de defesa do principado, incluindo as de madeira e de terra de Khotyn, e em seu lugar foram posteriormente erguidas outras de pedra. As primeiras muralhas de pedra poderão ter sido construídas ainda antes, na primeira metade do século XII, quando não cessaram os conflitos militares entre o Principado da Galícia-Volínia e o Reino da Hungria. O território do antigo castelo-cidadela de pedra localizava-se na parte norte do moderno pátio da fortaleza. A primeira fortaleza era pequena, com uma área de, no máximo, 2 hectares, rodeada por uma muralha e um fosso subtriangular com seis metros de largura. Apenas os restos da muralha, escondidos na espessura da cortina oriental, sobreviveram. Provavelmente, a principal estrutura defensiva era a torre no local onde se encontra a atual Torre Norte quadrangular.

Podia tratar-se de uma torre, imediatamente inscrita no sistema de muralhas, ou de uma torre de menagem separada, à qual foram posteriormente acrescentadas muralhas com cerca de trinta metros de comprimento, formando um pátio quadrado. Em meados do século XIV, ocorreu uma reconstrução parcial e reforço das fortificações de Khotyn: uma muralha desta época, com meio metro de espessura, encontrada a uma profundidade de 3,5 m da superfície atual, estendia-se ao longo do perímetro norte do Palácio do Comandante até à cortina oriental, atuando como muralha defensiva a sul. Estas medidas foram levadas a cabo na fase inicial da conquista dos territórios galegos pelos voivodas moldavos no curso superior dos rios Suceava, Siret e Prut.

Com a inclusão de Khotyn no Principado da Moldávia, na segunda metade do século XIV, a cidade adquiriu grande importância militar e política como ponto comercial e alfandegário na fronteira norte da Moldávia.

O rei moldavo Estêvão III, vulgarmente conhecido por Estêvão, o Grande (1457-1504), começou ativamente a fortalecer o sistema de defesa estratégica do principado moldavo, que consistia em 9 fortalezas, incluindo a de Khotyn. Isto deveu-se, provavelmente, ao desenvolvimento da artilharia a partir de meados do século XV.

Na década de 60 – início da década de 70 do século XV, o castelo de Khotyn foi completamente reconstruído e ampliado mais que duas vezes na direção sul, para um tamanho de aproximadamente 110 x 55 m. Muralhas e torres espessas (até 5 m) e altas (até 40 m) foram erguidas como proteção contra o tiro de canhão. Estavam decoradas com um ornamento de tijolos vermelhos – fileiras de imagens da “Babilónia” (provavelmente um símbolo da sabedoria arquitetónica) e do “Gólgota” (a rocha onde Cristo foi crucificado – um dos principais santuários cristãos). Muralhas decoradas desta forma adquiriram uma resistência adicional, protegidas também pelo poder da fé ortodoxa.

No início do século XVIII, o Império Otomano decidiu melhorar as capacidades de defesa da fortaleza. Segundo fontes históricas, em julho de 1713, “mais de 100.000 pessoas, 200 canhões grandes e pequenos, cavalos, equipamento e ferramentas para fortalecer a fortaleza avançaram em direção a Khotyn, pois era necessário fortalecer tanto a fortaleza como a cidade de Khotyn no Dniester”. De seguida, as brechas foram muradas, a torre sudoeste foi reconstruída com paredes muito mais espessas do que as anteriores, foi construída uma nova muralha defensiva e uma torre de portão, deslocando-as mais para sul. A expansão do castelo durante este período, entre outras coisas, é evidenciada pelos detalhes da arquitetura otomana utilizados no projeto das novas fortificações.

Simultaneamente à reconstrução da cidadela, os turcos construíram fortificações mais poderosas à sua volta – a Nova Fortaleza. O castelo perdeu a sua importância como objeto de defesa independente e passou a fazer parte de um novo sistema de fortificações, cobrindo a parte leste do pátio do recém-criado complexo de defesa e servindo de arsenal no futuro. Ora, a entrada da cidadela não necessitava de proteção adicional e, por isso, foi disposta na parede lateral leste da camada inferior da nova torre do portão superior, o que permitiu a rápida remoção de munições. As aberturas entre os pilares da ponte velha do século XV foram assentes com pedras, incluindo assim esta zona no sistema geral de fortificações exteriores.

Desde então até ao presente, a Fortaleza de Khotyn sofreu significativas alterações arquitetónicas como resultado de inúmeras guerras, batalhas no seu território e mudanças dos seus proprietários, mas a majestade e o poder do castelo, elevando-se sobre o Dniester, permanecem inalterados.