До XIV ст.
Заснування та ранні згадки
Замкова гора була заселена задовго до першої писемної згадки — а коли ця згадка нарешті з'явилася, вона розповідала не про заснування, а про облогу.
Задовго до будь-яких літописів на Замковій горі вже жили люди: археологічні дослідження початку 1970-х років зафіксували тут безперервні культурні нашарування від палеоліту через неоліт, бронзовий і залізний вік аж до наших днів. Знахідки скляних браслетів, кераміки та знарядь праці свідчать, що вже в XI–XII століттях це було значне культурне й економічне середовище Волині, а в X столітті на горі стояло городище, яке до XIII століття поступово набувало ознак справжнього міста.
Ширший контекст цих земель — розселення дулібського союзу племен у верхів’ях Західного Бугу й Прип’яті, який арабський історик Масуді у 40-х роках X століття називав «Valinana» (волиняни). У X столітті це племінне об’єднання ввійшло до складу Київської Русі як волинська земля, яка до 1170-х років лишалася залежною від Києва, а окремим князівством стала за Ізяслава Мстиславича, онука Володимира Мономаха. Кременець згадується серед укріплених міст південної частини тогочасного Луцького князівства — поряд із Перемишлем, Дубном, Стіжком і Даниловом.
Перша точно датована й надійно задокументована згадка про місто — не заснування, а облога. Навесні 1227 року, за уточненим дослідником Леонідом Махновецьким прочитанням Галицького літопису за Іпатіївським списком, угорський король Андрій II, ідучи походом, «прийшов до Кременця і бився під Кременцем, і багато угрів побили й поранили» — саме тут галицький князь Мстислав Удатний зупинив угорське військо.
Наступні десятиліття писали історію фортеці кров’ю. Готуючись до боротьби з монгольською залежністю, князь Данило Галицький укріплював прикордонні міста кам’яними баштами-«стовпами» — і Кременець разом із Даниловом лишився одним із небагатьох міст, які татарське військо так і не змогло здобути. Легенда приписує це зимовій облозі 1240 року під проводом хана Гуюка: нібито захисники облили гору водою, перетворивши її на кригу. Сам же переказ джерела ставлять під сумнів — водного джерела на вершині не було, і радше свою роль відіграла звичайна відлига з морозом. 1255 року хан Куремса плюндрував околиці, намагаючись змусити місто до покори; кременецький посадник Андрій, запідозрений у нещирості до Данила, поплатився за це життям від рук татар, але сам Куремса Кременця так і не взяв.
Найдавніший точно датований епізод, після якого фортеця на певний час перестала існувати, — 1261 рік: за наказом хана Бурундая князь Василько розібрав дерев’яні укріплення міста. Пізніша місцева традиція, яку фіксує kremenec.at.ua, наводить фразу Михайла Грушевського про Кременець як «діамант полудневої Волині» — оцінку вже сформованого міста, що добре передає, яким запам’ятався Кременець наступним поколінням дослідників.