Точно и однозначно установить время возникновения замка Каменец-Подольского невозможно. Ученые археологи и историки датируют возникновение каменного замка в Каменец-Подольском 13-тым – начало 14 века. Замок возводили братья князья Кориатовичи, которые правили Подольским княжеством в 60-90-х годах 14 века.
В 15 веке кроме Замка появляются каменные башни городских укреплений и стены с бойницами (комплекс сооружений Польских врат), а сама крепость за описанием в 1492 году (самое первое письменное описание замка, Каменец-Подольского) состояла из башен и каменных стен с двумя вратами на юг и север.
В 16 веке появляется комплекс Русских врат (как оборонные укрепления города), а крепость дополняется новыми башнями (Папская, Колпак, Тенчинская, Ляцкая, Новая Западная, Рожанка, Лянскорунская, Водная, Черная) и валами. В крепости был предусмотрен также целый ряд подвалов для сохранения оружия, пороха, продовольствия и военные казармы.
В первой четверти 17 века, когда Каменец-Подольский находился в составе Речи Посполитой, Старый замок дополняется комплексом сооружений Нового замка. Такие дополнения были вызваны широким использованием огнестрельного и артиллерийского оружия. Польша была заинтересована в создании такого форпоста на своих юго-восточных границах, который смог бы стать на пути турков и татар. В 1672-1699 годах крепость, Каменец-Подольского, находилась под властью Османской империи. Турки отстроили все разрушенные башни и стены, возвели новые здания.
В 1793 году крепость как и город переходит под власть Российской империи. Замок Каменец-Подольского в этот период русские используют в качестве военной тюрьмы, а крепость теряет свое военно-оборонное значение.
