Historia mały|lewo|Jar Smotrycza w Kamieńcu Podolskim W pierwszych wiekach naszej ery na miejscu dzisiejszego Kamieńca Podolskiego istniała forteca zwana Klapidava (także zwana Petridavą), która prawdopodobnie została zniszczona przez Hunów. Pierwsza wzmianka o mieście w źródłach ormiańskich pochodzić miała z 1062 roku i mówić o Kamieńcu jako o ormiańskiej faktorii handlowej. Prawdopodobnie założycielami Kamieńca Podolskiego byli litewscy KoriatowiczeSłownik geograficzny Królestwa Polskiego i innych krajów słowiańskich, Tom III.. Możliwe, że niedługo potem miasto zostało tymczasowo opanowane przez Kazimierza Wielkiego, następnie znajdowało się ponownie pod rządami władających Podolem litewskich książąt Koriatowiczów starających się zachować maksimum niezależności dzięki politycznemu balansowi pomiędzy Polską (okresowo w latach 1366–1370 byli lennikami Kazimierza Wielkiego), Wielkim Księstwem Litewskim oraz Węgrami. Z 1375 roku pochodzi pierwsza wzmianka o obecności w Kamieńcu zakonu dominikanów i ich klasztoru pod wezwaniem św. Mikołaja. W 1378 roku miasto zostało siedzibą nowej katolickiej diecezji podolskiej.