La tradizionale impostazione storiografica riteneva che il castello di Kam"janec'-Podil's'kyj fosse stato fondato durante la seconda metà del XIV secolo, poiché i primi resoconti storici accurati del castello risalgono alla metà del Trecento, cioè a quando la maggior parte dei territori della Rus' occidentale era finita sotto il controllo del Granducato di Lituania.[1] Una testimonianza importante risale al 1374: un documento scritto dal principe Karijotas in quell'anno, nello specifico, riferiva che le norme del diritto di Magdeburgo sarebbero state esposte a Kam"janec' all'interno del castello.[2] Ad ogni modo, gli scavi archeologici durante gli anni '60, hanno fornito prove contrastanti, le quali suggeriscono che la struttura potrebbe risalire ad un'epoca anche antecedente, ovvero alla fine del XII o all'inizio del XIII secolo.[3] È altresì chiaro dall'analisi dei reperti storici e archeologici che una fortezza di collina esisteva nell'area ed era sotto il controllo degli slavi orientali della Rus' di Kiev, anche se la fortificazione non si trovava sul sito esatto dell'attuale castello.[4]

Il vecchio presidio si rivelò col tempo obsoleto, ma occorreva comunque in qualche modo difendere la strategica posizione di Kam"janec' e le vicine rotte commerciali: a tal fine, il voivoda di Cracovia, Spytek di Melsztyn, iniziò a modernizzare il complesso all'inizio del XV secolo.[5] Durante le fasi di ricostruzione, si ristrutturarono le vecchie torri e se ne aggiunsero dieci nuove. Un secolo e mezzo dopo, il castello subì nuovi interventi, questa volta ad opera dell'ingegnere militare e architetto Hiob Bretfus, responsabile della realizzazione della Nuova Torre Occidentale e di quella orientale, delle mura orientali del castello e di una galleria sotterranea, così come di alcuni ingressi e degli alloggi per i collaboratori dello starosta (un funzionario reale) della città.[6]

Tra il 1350 e la metà del XV secolo, il castello di Kam"janec'-Podil's'kyj si trovava su una delle principali frontiere della Confederazione polacco-lituana. Dal 1434 e fino alla sua annessione da parte dell'impero russo nel 1793, il castello svolse un ruolo importante nella difesa contro le invasioni cosacche, ottomane e tartari in arrivo; dal XV al XVII secolo, la roccaforte fu attaccata da orde tartare per un totale di 51 volte.[7] Le invasioni tartare del 1448, 1451, 1509 e 1528, così come l'assedio ottomano del 1533, causarono danni sia al castello che alla città, ma tutte queste invasioni furono respinte con successo.[7]

Il castello di Kam"janec'-Podil's'kyj svolse un ruolo importante durante la rivolta di Chmel'nyc'kyj tra il 1648 e il 1654, quando i cosacchi di Zaporižžja, guidati dall'etmano Bohdan Chmel'nyc'kyj, si allearono con i tartari di Crimea e i contadini ruteni locali contro l'esercito e la milizia della Polonia-Lituania. Durante la sommossa, il castello fu assediato invano dai cosacchi del posto e dagli insorti guidati dal comandante Maksim Krivonis.[8] Nel 1651, il castello patì un'altra aggressione cosacca guidata dall'etmano Ivan Bohun, prima che un inaspettato contrattacco da parte degli insorti polacchi sotto i comandanti Aleksandrenka e Čuika ristabilisse la presenza confederata nell'area. Un esercito di 60.000 combattenti, guidato da Chmel'nyc'kyj in persona, riaffermò il controllo cosacco sul castello nel 1652.[9] Solo un anno dopo, il castello fu attaccato ancora una volta, in quest'occasione da 40.000 tartari di Crimea.[9]

All'inizio dell'agosto del 1672, un totale di 300.000 soldati ottomani guidati dal sultano Mehmed IV e una forza combinata di 40.000 tartari e cosacchi condotti dall'etmano Petro Dorošenko si presentarono alle porte della roccaforte.[10] Dopo aver condotto dei negoziati con gli aggressori, i capi della città si arresero al controllo della fortezza agli osmanici il 18 agosto. In segno di protesta, il comandante della fortezza Michał Wołodyjowski e il maggiore Hejking fecero esplodere la polvere da sparo rimanente del castello, uccidendosi insieme a 800 difensori.[11] Da allora e 27 anni dopo l'attacco, la fortezza servì come centro principale dell'eyalet di Podolia.[2] La pace di Carlowitz del 1699 vide il ritorno della supremazia polacca sull'area dopo che gli ottomani dovettero abbandonare la regione.[1]

Dall'inizio del XVIII secolo, il castello di Kam"janec'-Podil's'kyj aveva perso il suo ruolo difensivo e venne utilizzato più come prigione militare che come fortificazione difensiva.[6] Tra i reclusi e i giustiziati principali figurarono negli anni staršiná (ufficiali), haidamaka e anche il pretendente che all'età aveva tre anni al trono polacco, Stanislao II Augusto Poniatowski.[12]

Anche se aveva perso il suo carattere difensivo, il sito si rivelò uno dei più robusti della Confederazione fino alla seconda spartizione della Polonia del 21 aprile 1793, quando sia il castello sia la città passarono sotto la sovranità dell'impero russo.[13][14][15] Lo stesso giorno, il comandante del castello consegnò la chiave della struttura ai nuovi padroni e giurò fedeltà all'impero nella cattedrale della città.[15] 101 cannoni d'artiglieria in seguito accompagnarono la decisione del comandante all'interno del castello sparando a salve.[15] Durante la campagna di Russia del 1812, una guarnigione dell'esercito imperiale russo rimase di guardia nel castello. Nel 1815, Konstantin Batjuškov, che in seguito divenne un noto poeta e scrittore, fu di stanza in qualità di ufficiale nella fortificazione.[16] Nel 1846, anche il poeta Vladimir Raïevski prestò servizio militare del castello: durante quella fase, egli istituì un'organizzazione filo-decabrista di ufficiali dell'esercito dalla mentalità progressista.[16]

Dal 1816 fino al 1914, la fortezza fu trasformata da prigione militare in carcere per debitori, criminali e prigionieri politici.[17] Nel 1831, il lessicologo russo Vladimir Dal' lavorava nel castello, all'epoca scriveva un dizionario della lingua russa.[5] Il castello era il centro del movimento anti-feudale nella Podolia durante il XIX secolo guidato dal veterano di cavalleria della guerra patriottica del 1812 Ustim Karmeluk (1787-1835), oggi considerato dagli ucraini un eroe popolare nazionale.[18]

Dopo una serie di cambiamenti politici a seguito della rivoluzione del 1905, i partiti e le organizzazioni politiche furono ammessi dalla legge in tutto l'impero russo. Nel 1906, nel castello aveva sede un totale di 67 organizzazioni politiche: tra questi c'era il giornale "Iskra" (Scintilla) del Partito operaio socialdemocratico russo.[19] Un decreto emesso dal Consiglio dei commissari del popolo della RSS Ucraina nel 1928 dichiarò il complesso del castello di Kam"janec'-Podil's'kyj una riserva storico-culturale.[20] Alla fine degli anni '30, fu pianificata la trasformazione del castello in un museo e nel 1937 si iniziarono i lavori di ricostruzione degli edifici.[20] Tra le attrazioni del museo si aggiunse una scena raffigurante Karmaliuk nella cella di prigione del castello nella cosiddetta torre papale, dove fu tenuto durante la sua prigionia nel castello. Il numero di visitatori della struttura durante gli anni '30 raggiunse i 300.000 turisti all'anno.[20]

Nel 1947, il castello di Kam"janec'-Podil's'kyj fu inserito nell'elenco delle riserve storiche di tutta l'URSS.[20] Una placca commemorativa e un bassorilievo dedicato a Karmaliuk furono eretti vicino all'esposizione allestita in loco il 18 aprile 1958.[20] Dal 1962, i lavori di restauro e di archeologia vennero condotti nel castello sotto la supervisione degli architetti Y. Plamenjtska e A. Tjupjč.[21] Il 18 maggio 1977 si istituì la riserva nazionale storico-architettonica di "Kam"janec'".[22] Il 13 settembre 1989, il governo della RSS Ucraina presentò una richiesta di designazione della zona tutelata nell'elenco dei patrimoni dell'umanità curato dall'UNESCO.[23]

Nel 2004, la riserva fu trasformata in un distretto nazionale di conservazione da un provvedimento normativo.[24] Il 21 agosto 2007, il complesso è stato dichiarato una delle sette meraviglie dell'Ucraina, classificandosi al terzo posto nel processo di assegnazione di questo riconoscimento nazionale.[25] Una forte tempesta avvenuta il 1º agosto 2011 distrusse parzialmente la Nuova Torre Occidentale; in quell'occasione, l'ufficio del sindaco della città non negò che l'integrità strutturale della torre era stata indebolita durante la sua ultima ricostruzione nel 2007, aprendo la strada al suo crollo appena quattro anni dopo.[26]