За Червенские города Русь вновь воевала с Польшей в 992 году. Затем, пользуясь усобицами сыновей Владимира, Польша снова захватила этот край в 1018 году, но в 1030 году Ярослав Мудрый опять выбил поляков отсюда. Пограничный характер Холмщины привел к тому, что за этим небольшим, но важным краем закрепилось понятие «украйны» (как и за другими окраинными территориями Руси). Так, в Ипатьевской летописи под 1213 годом говорится, что князь Даниил Галицкий взял забужские города и всю «украйну». Но, собственно, ни Волынь, ни Галичина тогда не считались «украйной». Эти земли были частью Руси. Зато поляков, жителей граничащей с Холмщиной территории, русские летописцы называли «ляхове украиняне»[211].

Вероятно, именно в это время появляется на свет город Холм, хотя неясно время возникновения города. В Галицко-Волынской летописи рассказ об основании Холма записан под 1259 годом в связи с описанием пожара. По-видимому, на месте Холма раньше существовало неукрепленное поселение, в котором жили восточные славяне. Позже это поселение переросло в город. Об этом свидетельствуют деревянные конструкции на валах и керамика XI века, найденная здесь археологами. По свидетельству польского летописца Длугоша, в 1074 году в Холме правил некий князь Григорий.

Сохранилась легенда о том, что на холме, давшем название городу, находилась языческая святыня. Согласно преданиям, когда на нее напали враги, то отбиться от неприятеля защитникам святыни помог белый медведь, который вышел из недр горы. И поныне белый медведь изображен на гербе Холма.

Город Холм, вероятно, потому и не был указан летописцами, что в нем не имелось серьезных оборонительных укреплений, по крайней мере, до 1241 года, когда Холм не смогли взять татары. Создателем города как крепости и своей столицы стал Даниил Галицкий. По преданию, князь спросил у местных жителей: «Како именуется место се?» – и получил ответ: «Холм ему имя есть»[212]. Даниил построил в Холме мощные укрепления («град иный, его же татарове не нозмогоша прияти, егда Батый всю землю Русскую пойма»[213], писали летописцы) и почти постоянно находился в городе, который, таким образом, стал стольным градом Галицко-Волынского княжества. Чтобы еще более развить город, Даниил стал щедро привлекать переселенцев со всех краев: «Данило нача призывати приходне немциирусь, иноязычники и ляхи. Идяху день и во день и уноты и мастери всяции бежаху ис татар, седельници, и лучници, и тульници и кузнеци железу, и меди, и серебру; и бе жизнь, и наполниша дворы окрест, поле и села»[214]. Как видим, Холм во времена князя Даниила был чем-то вроде Санкт-Петербурга при Петре I – новый город, основанный державной волей правителя, стоящий прямо возле вражеского рубежа, быстро заселяемый смешанным населением. Вероятно, Холм привлекал внимание Даниила не только своими укреплениями, но и тем, что находился на стыке обоих владений князя – Галицкой и Волынской земель, а также определенной отдаленностью от татарских набегов. В Холме Даниил умер и был похоронен.