«Четверо братьев, четверо князей Кориатовичей, племянников великого князя Ольгерда, отправились однажды на охоту. Места возле реки Смотрич были тогда дикими, нехожеными, водилось здесь зверя разного в большом количестве. И вот увидели братья на лесной поляне большого оленя красоты неописуемой. Погнались за ним славные наследники рода Кориатовичей, вскипела в их жилах охотничья кровь. Взвились на дыбы горячие кони, стремглав понеслись сквозь лесную чащу. Но и олень скакал быстрее ветра, не подпускал к себе охотников. Долго гнались Кориатовичи за зверем, пока не вывел он их на уступ скалы, возвышавшейся над огромной пропастью. И вмиг забыли братья об олене, настолько прекрасным был открывшийся сверху вид. „Здесь мы заложим наш город, и никто, ни один враг не ступит на эту землю!“. И вырос город, названный Каменец, и стали править в нем братья Кориатовичи».
Наверное, с точки зрения исторической правды процесс превращения небольшого феодального поселения, возникшего на месте древнеримского города, в крупный город, постепенно ставший центром Подолья, выглядит гораздо правдивее, чем изложенная выше легенда. Но Каменец-Подольский настолько красив, настолько необычен, что такая красивая легенда просто не могла не появиться. И все-таки нужно отметить, что развивался и строился Каменец-Подольский благодаря умелым и упорным ремесленникам и купцам, облюбовавшим эти места. С точки зрения торгового человека, город был расположен просто идеально, на самом перекрестке европейских торговых путей — тут тебе и издавна известный путь «из варяг в греки», дорога от Балтийского до Черного моря, и граница между Европой и Диким Полем, тут тебе и разные народы, и у каждого есть что-то, что можно выгодно купить и не менее выгодно продать. А чтобы защитить нажитое, не дать лихим людям безнаказанно грабить дома и мастерские, где день и ночь работали ремесленники, отчисляли деловые люди немалые средства на строительство мощных укреплений. Вот почему многие башни Каменец-Подольской крепости до сих пор носят вполне мирные названия — Гончарная, Скорняжная, Портняжная, Ковальская.
Как бы там ни было, кто бы ни основал Каменец-Подольский, а город развивался своим путем. Литовцы, отбившие у монголо-татар крепость на Смотриче, правили в Каменец-Подольском до 1434 года. За это время он превратился в крупный торговый, культурный и военный центр, на рубеже XIV и XV столетий город получил магдебургское право. Не меньше внимания «бастиону Европы» уделяли и польские короли, владевшие Каменец-Подольским на протяжении нескольких веков. На город по-прежнему возлагалась очень важная функция — служить оплотом, надежной защитой границ королевства от нападений татар и других кочевых племен. В 1464 году специальным указом польского короля Каменец-Подольский был провозглашен Королевским городом. В это время в городе началось бурное строительство, были возведены новые каменные стены, построены кафедральный, доминиканский, францисканский соборы, ратуша и другие сооружения. Серьезно была укреплена и достроена крепость, на вооружении которой состояло 12 самых мощных по тем временам пушек. И все эти меры не были напрасными, ведь Каменец-Подольский неоднократно подвергался нападениям неприятеля. Помимо татар, город осаждали турецкие войска, дружины под командованием молдавских господарей. Пытались взять крепость над Смотричем и украинско-русские войска под командованием гетмана Богдана Хмельницкого. Однако мощные стены служили надежной защитой польского гарнизона, который, несмотря на свою немногочисленность, успешно отбивал все атаки противника.