Впервые Полонное упоминается в Лаврентьевской летописи в 1169 голду. В летописи четко сказано, что половцы не взяли города, а только беспощадно ограбили окрестности. Город от основания и до 1195 принадлежал киевским князьям. Сама же крепость, очевидно, была построена в конце X века - в 996 году Владимир Великий приписал Десятинной церкви десятую часть своих «градов» (городов). Среди них было и Полонное, недаром летописец называет его «святой Богородицы град Десятинный». Археологические исследования 1992-1993 годов, проведенные в Полонном археологической экспедицией Каменец-Подольского педагогического института под руководством Винокура И. С., подтвердили существование укрепленного городища площадью примерно 8,2 га в X-XIII вв. Укрепление находилось в районе современной ветеринарной больницы, на естественном возвышении, которое окружено водами реки Хоморы и фактически является полуостровом. Полуостров, возвышался на 12-17 метров над окружающей местностью, был обнесен валом и огорожен частоколом. С единой не прикрытый рекой стороны крепости (территория современного костела Св. Анны) в XII в. появляется Мысовое поселение, которое тоже было укреплено частоколом. Крепость летом была фактически неприступной - низкие, болотистые берега Хоморы защищали город от врага.
Начиная с конца XII в. и в XIII в. Полонская крепость, вместе с Микулином на Хоморе и Каменцом на Случи были порубежными городами Волынского княжества, а впоследствии Галицко-Волынского княжества. В частности, в 1196 году Роман Мстиславич повелел своим людям с Полонного напасть на волость князей Киевского Рюриковичей.
Крепость, очевидно, была разрушена монголо-татарами в 1240 году. Галицко-Волынская летопись повествует о существовании Полонского монастыря в 1255-1257 годах. Однако именно о крепости четких упоминаний в древнерусских летописях уже нет.
Среди скупых упоминаний этого времени в соглашении от 1366 Казимира III с Любартом среди шести «каменных» городов фигурирует и Полонное. А в 1394роци князь Витовт, который взял себе значительную часть украинских земель, передает Полонное князю Глебу Святославичу. Когда в 1494 году Полонное становится собственностью Михаила и Константина Острожских, Константин обращается к королю с просьбой о предоставлении разрешения на реконструкцию крепости. В 1510 году Константин Острожский строит, по сути, новую крепость - на месте бывшей, куда теперь переместился центр города.
Полонное при Острожских ни разу не было захвачено татарами, набеги которых тогда становятся все более частыми.
На европейских картах XVI в. (Карты Герарда Меркатора 1554, Каспра Вольпи 1556, Вацлава Гродецкого 1562) Полонное изображенно как хорошо укрепленный город.
До 1621 году город и крепость, с незначительными перерывами, находится в собственности князей Острожских. В 1574 году упоминается деревянный замок Константина-Василия Острожского. С 1621 Полонное становится собственностью Станислава Любомирского. Тогда Полонская волость состояла из Полонного с дерева крепстью и 76 сел.
Любомирский превратил город в мощную волынской крепость. В 1640 году он укрепил центр города земляными оборонительными валами по пятиконечнму плану, укрепил стены замка и крепостные стены. В крепости находились 80 пушек, а припасов должно было хватить на три года. Автором перестройки крепости был итальянский архитектор Мацей Трапола. (Существует также версия, что проектировал новые укрепления Кшиштоф Мерошевского). Как важный оборонительный пункт изображенное Полонное на карте военного инженера и топографа Боплана от 1647.
С началом освободительной войны казацкие полки Максима Кривоноса 10 июля 1648 подошли к Полонному, которое, по словам М.Кушевича, было «большое и неизмеримо лучше для обороны, чем Львов». В распоряжении Полонского старосты Яндзецкого была залога численностью 1200 солдат и 700 шляхтичей, 80 пушек, большой запас пороха и продовольствия. Однако уже 11 июля, после боя, казаки заняли пригороды. Они наладили связь с солдатами, набранными из украинских мещан и крестьян, а также с жителями города. 12 июля жители города помогли казакам захватить крепость и все имущество. Повстанцы уничтожили польский гарнизон, перебили евреев, захватили много пленных, оружия, провианта и другой добычи на общую сумму 4 млн злотых.
Известие о падении Полонской крепости вызвало массовые побеги шляхты с территории Юго-Восточной Волыни. Альбрехт Радзивил утверждал, что напугана шляхта без всякой обороны покинула Заслав, Острог, Корец, Междуречья.
Хотя основные силы повстанцев покинули город, в Полонном разместился казацкий отряд. Он поддерживал связь с казаками в Чертории. Тогда Полонное было сотенным городом Волынского казацкого полка.
В мае-июне 1649 начались жестокие бои между польскими войсками и казаками Украинский Юго-Восточной Волыни. Большинство украицев отступила за Случь. Казаки оставили также Полонскую крепость. А.Фирлей предлагал королю 19 июня 1649 дать приказ киевскому воеводе занять Полонное. Однако поляки не успели этого сделать - уже 26 июня 1649 польские войска начали отступление в Збараж. Полонская крепость, по сути, оставалась пустой. Поэтому после подписания Зборовского договора татарские отряды впервые в истории захватывают Полонное. В январе 1649 года в междуречье Случи и Горыни находятся отряды Данила Нечая. Поляки снова занимают Полонскую крепость только в 1650 году. Но уже в 1651 году украинские войска вновь возвращают себе Полонное, взяв крепость и уничтожив весь польский гарнизон.
После битвы под Берестечком Полонская крепость пустовала. В августе 1651 польское войско, которое двигалось на Любарта, даже не заходило в Полонное. В 1653 году татары, а впоследствии и украинские войска под командованием Демьяна Лисовца разбивают польские подразделения под Полонным, но крепости не занимают. О том, что в крепости не было польских войск, свидетельствуют сейму инструкции 1655 года, в которых шляхта требует у короля разместить в Полонном войска. Только в первой половине 1657 гетман Богдан Хмельницкий приказал украинским полкам занять территорию Погориння. Казацкие полки освободили Полонное, Острог, Гощу, Корец и оставили в этих местах мощные гарнизоны. В Полонном разместилась Полонская сотня восстановленного Волынского полка. Несмотря на почти непрерывные военные действия, состояние крепости был достаточно неплохим. Это видно из того, что здесь некоторое время находился каштелян волынский Станислав Беневский. С 1658 и по 1661 в Полонном находился гетман Иван Выговский с сильным казацким гарнизоном. В 1661 шляхта снова просит у сейма все же прислать польский гарнизон в Полонскую крепость.
Однако крепость не была полностью разрушена и выполняла свои функции. Так, в августе 1672 казацкий полк Михаила Ханенко, который находился тогда на службе Речи Посполитой, замыкался в Полонном, чтобы пересидеть опасность от нападения турецко-крымского войска. Постоянного польского гарнизона в крепости так и не было. Об этом свидетельствует тот факт, что осенью 1672 жители Полонного послали своих представителей в Паволоцкого полковника Григория Гамалеи, пригласили в город залога украинского войска и поклялись украинском государстве. Но после прекращения в 1675 году существования Паволоцкого полка, залога которого стояла в Полонном, город и крепость перешли в состав Волынского воеводства Речи Посполитой.
В 1702 году владелец города, князь Юрий Любомирский, созвал шляхту Волынского воеводства собираться в Полонном для похода против казаков Палия. Во время Северной войны гетман Украины Иван Мазепа с войсками занял Волынь и на некоторое время (1704-1706) основал в Полонном главную квартиру. Российский и украинский гарнизоны занимали крепость до 1711 года под командованием полковника Кошкеля и Киевского полковника Танского; в 1710 г. сеймик Волынского воеводства обращался к русским с предложением вернуть крепость Польше. В 1711 году Петр I вернул крепость Юрию Любомирскому, взыскав вознаграждение за укрепление фортификаций. Крепость считалась первоклассной, у нее сдавали на крепостные работы гайдамаков по приговору суда.
В 1792 году польская армия, которая отступала перед российскими войсками, пыталась основать в Полонном свою главную квартиру; сюда были свезены: военная казна, больные, различные материалы и провиант и отправлены инженеры для ремонта крепости. Однако крепость показалась им настолько разрушенной, что пришлось отказаться от предыдущих намерений и польская армия отступила дальше, оставив в Полонном запас провианта и часть испорченной артиллерии.