Secondo alcune fonti storiografiche la fortezza di Kremenec' fu costruita tra l'[[VIII secolo|VIII]] e il [[IX secolo]], e più tardi fu sotto il controllo della [[Rus' di Kiev]]. Le prime testimonianze nella letteratura antico-slava sono databili all'anno [[1226]] quando il governatore della città, Mstislav il Calvo, sconfisse l'esercito ungherese di Andrea II sotto le sue mura. Durante l'invasione mongola della Rus, nel [[1240]]-[[1241|41]] Kremenec' fu una delle poche città che [[Batu Khan]] non riuscì a conquistare.
La città ottenne i [[diritti di Magdeburgo]] nel [[1431]].
