El antiguo castillo fue reconstruido y ampliado por los reyes polacos para defender el sudeste de Reino de Polonia y la República de las Dos Naciones contra ataques de otomanos, tártaros, rumanos y moldavos. Tras el Tratado de Buczacz en 1672, la localidad se incorporó al Imperio Otomano como capital de un vilayato local, aunque los alrededores de la ciudad siguieron como territorio polaco y allí el rey Juan III Sobieski hizo construir una fortaleza en Okopy, la llamada Trinchera de la Santísima Trinidad. En 1699 la ciudad fue devuelta a la República de las Dos Naciones como consecuencia del Tratado de Karlowitz, mientras la fortaleza fue continuamente aumentada hasta ser considerada la más sólida de Polonia-Lituania, de hecho las ruinas de la fortificación conservan aún las balas de hierro de los cañones incrustados en sus muros debido a los cercos soportados.
Tras la segunda partición de Polonia en 1793 la ciudad pasa al Imperio Ruso, como capital de la gobernación de Podolia (Guberniya Podol'skaya). Una torre de la fortaleza fue usada a inicios del siglo XIX como prisión del rebelde campesino Ustym Karmeliuk que consiguió escapar de ella tres veces.
Con la Revolución de octubre de 1917 la ciudad quedó incorporada brevemente a la Ucrania independiente, y terminó integrada en la República Socialista Soviética de Ucrania en 1919. Durante la Guerra Polaco-Soviética (1919-1921) la ciudad fue tomada por las tropas polacas y luego devuelta a los soviéticos por el Tratado de Riga de 1921. A partir de esa fecha, la ciudad se integró plenamente en la Ucrania Soviética.
Si bien la mayoría de la población estuvo formada por polacos y ucranianos, el hecho que Kamienets-Podilsky fuera siempre un centro comercial importante de la región le dio un carácter multiétnico y multirreligioso, con minorías importantes de judíos y armenios. Bajo el régimen soviético, las minorías étnicas sufrieron discriminaciones varias, y la mayoría de la población polaca que permaneció en la zona después de 1922 fue deportada a Siberia. Durante la Segunda Guerra Mundial la ciudad fue tomada por la Wehrmacht a fines de 1941 y su minoría judía fue blanco de las políticas de exterminio nazi. Durante esa guerra, en sus cercanías se desarrolló la Batalla de Kamenets-Podolsky en 1944, y tras la contienda la ciudad se reintegró en la República Socialista Soviética de Ucrania.
