Kolejnym ważnym okresem w odległej historii Chełmszczyzny jest wczesnośredniowiecze, z którego to okresu pochodzą ślady ówczesnego osadnictwa w Zasłupiu (tak nazywano pola przy wieży, dzisiejszy Bieławin). Opierając się na odkryciach archeologicznych ze stanowisk o charakterze osadniczym i obiektach pod wieżą średniowieczną w Bieławinie stwierdzono, iż duża różnorodność wykopalisk sugeruje istnienie tu miasta zalążkowego, wyprzedzającego osadnictwo grodowe i miejskie na Górze Chełmskiej.

We wczesnym średniowieczu stosunki plemienne dalekie były od jednoznaczności obecnych podziałów narodowych. Najbardziej charakterystyczną cechą ziemi chełmskiej było jej przejściowe położenie między dwoma grupami Słowian: wschodnimi i zachodnimi. Plemiona jakie zamieszkiwały rejony Bugu to Dulebowie, Bużanie, Wołynianie i Lędzianie, których ośrodkiem był Sandomierz. Oni to pobudowali tu, na kresach swego terytorium, system obronny złożony z licznych grodów z Czerwienią na czele.

Po czym, jak podaje staroruski kronikarz Nestor w 981 roku obszar ten został opanowany przez księcia kijowskiego Włodzimierza. Był on potomkiem sławnego Warega czyli Wikinga, Rusa Ruryka. Nosił przydomek Wielki, ponieważ za jego panowania Ruś obejmowała ogromne tereny większej części dzisiejszej Rosji Europejskiej, państwa Bałtyckie oraz część Polski. „Idzie Włodzimierz na Lachów i zabiera im grody: Przemyśl, Czerwieńsk i inne miasta i te są do dnia dzisiejszego pod Rusią”.

Na przełomie XII i XIII w. Ruś była podzielona na liczne księstwa a w każdym z nich rządzili przedstawiciele rodu Rurykowiczów wywodzącego się od Waregów przybyłych w IX w. ze Skandynawii. Dla Polski ważne były księstwa halickie i wołyńskie. Do 1205 r. w obu księstwach władał zaprzyjaźniony z Piastami małopolskimi i mazowieckimi książę Roman. Gdy jednak zginął pod Zawichostem, na Rusi halicko-wołyńskiej zapanował chaos. W następnych latach o wpływy w tych księstwach rywalizowały Węgry z polskim księciem Leszkiem Białym. W końcu na tronie w Haliczu zasiadł syn Romana Daniel.

Pierwsza połowa XIII w. przyniosła ważne zmiany w dziejach Chełma. Istniejący w poprzednich wiekach gród „na Górce” oraz okoliczne osiedla będące jego zapleczem zostały zniszczone w czasie wojen rusko-polsko-węgierskich, a teren porósł las. W miejscu tym w latach trzydziestych XIII wieku książę halicko-włodzimierski Daniel wzniósł nowy gród kamienny i jednocześnie rozbudował podgrodzie chełmskie.
Właśnie w tym czasie, według słów autora Kroniki Halicko – Wołyńskiej stanowiącą część tzw. Latopisu Hipacowskiego, czyli rocznika historycznego, jednego z najstarszych zbiorów kronik staroruskich:

„Danielowi ksiąciu włodzimierskiemu, który zbudował gród Uhrusk i ustanowił w nim biskupa, jadącemu przez pola i czyniącemu łowy, ukazało się na górze miejsce piękne i zalesione, otoczone polem. I pyta tuziemców: jak nazywacie to miejsce? A oni odpowiedzieli: Chełm jest jego imię. I polubił to miejsce i pomyślał: zbudujemy na nim mały gródek i poświęcimy go Bogu i św. Janowi Złotoustemu i postawimy cerkiew imienia jego. I zbudował mały gródek i widział jak Bóg mu pomagał i święty Jan. I stworzył taki gród, że go Tatarzy wziąć nie mogli. Widząc książę Daniel, że Bóg sprzyja temu miejscu, zaczął przywoływać ludzi i przychodzili Niemcy i Ruś i różnojęzyczni i Lachy szli dzień w dzień. I majstrowie wszelacy, uciekający od Tatarów, siodlarze i łucznicy, blacharze i kowale na żelazo, miedź i srebro. I było życie i napełniły się dwory około grodu i wsie ...”

Zamek obronny księcia zajmował najwyższy szczyt Góry Chełmskiej. Pozostała część wyniosłości mieściła świątynie, mieszkania bojarów i ich rodzin oraz zabudowania gospodarcze otoczone odrębnymi obwarowaniami obronnymi. W ten sposób ukształtowany dwuczłonowy gród zajmował cały szczyt góry, stwarzając bardzo dogodne warunki obronne.

Nieopodal miasta w Stołpiu nad rzeką Garką i spływającym do niej rozlewiskim ze źródlaną wodą znajduje się po dzień dzisiejszy mały, kopcowaty nasyp, starego gródka i włączona w ten nasyp kamienna, tajemnicza wieża zachowana do wysokości ponad 19 m. Na podstawie badań archeologicznych oraz podań spisanych przez chełmskiego biskupa Jakuba Suszę w 1684 r. zespół zabytkowy w Stołpiu miał pełnić funkcję sakralno-rezydencjalną. Zarówno w samym Stołpiu jak i w pobliskich okolicach występują liczne źródełka uważane niegdyś za magiczne. Stąd miejsca te wykorzystywane były do uprawiania kultów pogańskich. Według wieżeń jeden z dwóch legendarnych książąt Polan (założyciel Kijowa około VIII w.) Sczek lub Choriw, miał mieć w Stołpiu pałacyk lub zameczek i świątynię pogańską w Podgórzu.

Przypuszcza się, iż sama budowla została wzniesiona w  XIII wieku, kiedy terenami tymi rządzili Romanowiczowie. Styl świątyni jest charakterystyczny dla wczesnochrześcijańskich budowli chrzcielnych, tzw. babtysterii występujących na terenach Bizancjum. Wpływy tak odległej cywilizacji na Chełmszczyźnie można wytłumaczyć zabiegami dyplomatycznymi. Dzięki nim dochodziło do zawierania małżeństw pomiedzy sąsiadującymi rodami. Jednym z takich był ród Romanowiczów. Stąd uważa się, iż książę Daniel przenosząc stolicę swego księstwa do Chełma  ufundował, w miejscu dawnego kultu pogańskiego, świątynię dla swojej matki. Obraz po lewej przedstawia spotkanie księcia Rusi Kijowskiej Światosława z cesarzem Bizancjum Janem Tzimiskesem w X w.

Mongołowie, którzy za Czyngis-chana stworzyli wielkie mocarstwo, w 1238 r. uderzyli na Ruś. W 1240 r. padł Kijów i cała Ruś znalazła się pod jarzmem mongolskim. Rok później złota horda, czyli wyprawa armii mongolskiej dowodzona przez Batu-chana ruszyła na zachód. Jej celem były Węgry.

Chcąc uniezależnić się od Tatarów, książe Daniel przeniósł swoją stolicę z Halicza do Chełma, który znalazł się na ważnym szlaku handlowym biegnącym od Włodzimierza Wołyńskiego na zachód oraz północ do Bałtyku. Szlak ten łączył ośrodki handlowe znad Morza Czarnego, szczególnie Kaffę, z zachodnią Europą.

Chełmski gród, napadnięty w 1240 roku przez Mongołów, oparł się najazdowi pod wodzą Batu-Chana, ale w tym samym czasie wybuchł pożar zaproszony przypadkowo przez ”pewną babę”, który zniszczył osiedle. Ogień był tak duży, że łuna była widoczna na całej ziemi Chełmskiej a nawet podobno w odległym Lwowie. Książę odbudował gród po pożarze i dzięki jego staraniom Chełm stał się głównym ośrodkiem regionu.

W 1260 r. powstała nowa cerkiew, była to katedra Narodzenia Przenajświętszej Bogurodzicy, w której umieszczono nową ikonę z wizerunkiem Matki Boskiej (to właśnie ta ikona stała się po latach słynącym cudami obrazem Matki Boskiej Chełmskiej).

Daniel, opierając się na silnych grodach zjednoczył szereg księstw ruskich od Kijowa po Karpaty i Prypeć. Kiedy zagrażali mu Tatarzy, w celu uzyskania pomocy ze strony krajów katolickich, nawiązał stosunki z papieżem Innocentym IV, przyjął katolicyzm i otrzymał koronę królewską. Nie koronował się w Chełmie, lecz w Dorohiczynie w 1233 roku na króla Rusi. Stosunki z Rzymem były krótkotrwałe. Daniel zmarł w 1264 r. w Chełmie i tam został pochowany.

Po śmierci Daniela rezyduje w Chełmie Szwarno, który zyskuje część ziem litewskich, aczkolwiek częściej przebywa w Nowogrodzie Siwierskim. W tym czasie toczą się między Lublinem a Chełmem zacięte walki Polaków z Rusinami. Chełm okazał się wtedy twierdzą nie do zdobycia. Pod względem etnicznym dominowała ludność ruska, z pewnym udziałem Polaków, Niemców i prawdopodobnie Żydów.
Okres rządów następców księcia Daniela przyniósł stopniowy upadek Księstwa Wołyńskiego. Sytuacja polityczna i militarna, w której coraz częściej brali udział Litwini i Krzyżacy, nie sprzyjała rozwojowi Chełma. Zjednoczenie, po rozbiciu dzielnicowym, ziem polskich przez Łokietka, a następnie wzmocnienie państwa przez Kazimierza Wielkiego miały decydujący wpływ na los Rusi Chełmskiej i Chełma.

W 1338 r. książę halicki Bolesław Jerzy Trojdenowic zawarł z Kazimierzem układ dynastyczny, w którym przekazał królowi polskiemu po swej bezpotomnej śmierci księstwo halicko-włodzimierskie. Gdy 2 lata później został otruty przez bojarów, nie doczekawszy się potomka, Kazimierz natychmiast wyruszył na wschód, zajmując całe Księstwo Halickie.

Jednakże pełne opanowanie Rusi halicko-wołyńskiej nie było łatwe. Możni haliccy i włodzimierscy byli podzieleni. Ponadto miał Kazimierz konkurentów. Do władzy w Haliczu i Włodzimierzu pretendowali również Tatarzy oraz Litwini. Należało się też uważnie przyglądać działalności Węgrów. Królowie węgierscy, Karol Robert, a potem Ludwik, byli sojusznikami Polski, ich wojska niejednokrotnie wspierały polskie oddziały walczące na Rusi. Jednocześnie jednak toczyła się cicha polsko-węgierska rywalizacja o Ruś.
Rywalizacja polsko-litewska o ziemie Księstwa Wołyńskiego wzmogła się pod koniec lat czterdziestych XIV w. Wykorzystując porażkę Litwinów w wojnie z Krzyżakami w 1349 r. król Kazimierz rozwija ekspansję na wschód czego wynikiem była wyprawa na nadbużańskie tereny księstwa, kiedy to między innymi zdobyto Chełm, Bełz i Brześć.

„zamek chełmski szturmowano przy użyciu ciężkich kusz, z których nieustannie miotano pociskami.” - Jan Długosz.

Po tym jak ziemia chełmska stała się lennem Królestwa Polskiego, wtedy to podjęto starania w Rzymie o utworzenie biskupstwa chełmskiego. 20 maja 1359 r. nominację, wydaną przez Papieża Innocentego VI, na pierwszego biskupa chełmskiego obrządku rzymskiego otrzymuje Tomasz Franciszkanin.

Tymczasem o tereny te wciąż toczą się walki pomiędzy Polską a Litwą. Już w 1351 r. Litwini zdołali odbić te obszary z rąk polskiego króla. Władzę w Chełmie przejął książę Jerzy Narymunowicz.
Niebawem jednak, bo już w 1366 na skutek pomyślnej wyprawy króla Kazimierza Wielkiego przeciwko Litwie, Polska odzyskała gród Chełm wraz z zamkiem. Po zwycięstwie nad Lubartem, synem wielkiego księcia litewskiego Giedymina, zawarto pokój, na którego podstawie Litwa odstępowała Polsce ziemie nad górnym Bugiem, ziemię chełmską i bełską, część Polesia po Luboml i Ratno, prawie całą Ziemię Włodzimierską i Krzemieniec. Ziemię Chełmską i Bełską otrzymał jako lenno książę Jerzy Bełski Narymuntowicz. Po 10 latach łamiąc układ lenny, wspólnie z Lubartem i innymi książętami litewskimi brał on udział w najazdach na Polskę, odrywając od niej ziemie chełmską i bełską.

Strona polska, a zwłaszcza król Ludwik Węgierski nie zrezygnowała z utraconych ziem. Król postanowił odzyskać te ziemie i dlatego zorganizował w 1377 roku polsko – węgierską wyprawę wojenną. Wysłał rycerstwo krakowskie i sandomierskie pod wodzą starosty krakowskiego Sędziwoja z Szubina na zajęte ziemie w celu zdobycia zamku chełmskiego, sam zaś poszedł pod Bełz. Wojska polskie po ośmiu dniach oblężenia Chełma zdobyły zamek, a następnie zajęły kolejno Grabowiec, Horodło, Zawłocie. Książę Jerzy Narymuntowicz został usunięty z Bełza i Chełma. Odebrane mu terytoria zostały oddane w zarząd wielkorządcy Rusi z ramienia króla Ludwika, księcia Władysława Opolczyka, a w 1378 r. przeszły wraz z całą Rusią Czerwoną pod bezpośredni zarząd węgierski. Nowy układ polityczny nie trwał jednak długo.

Unia polsko – litewska z lat 1385-1386 wprowadziła zasadnicze zmiany w sytuacji całego terytorium. Po objęciu tronu polskiego król Władysław Jagiełło zorganizował wyprawę, na której czele stanęła królowa Jadwiga. Po opanowaniu Rusi Halicko-Wołyńskiej podzielił sporne ziemie ruskie na szereg małych księstw, nad ziemią chełmską zaś przejął rządy osobiście, włączając ją do Korony Polskiej. Od tej pory Chełm ściśle związany z dziejami państwa polskiego.

Chełm w okresie przedlokacyjnym, czyli kiedy jeszcze nie miał praw miejskich w XIII i pierwszej połowie XIV wieku rozwijał się głównie dzięki wymianie handlowej między Rusią a Bałtykiem (Włodzimierz – Toruń), jak też dzięki ożywionym kontaktom gospodarczym z zasobnym zapleczem rolniczym.
Wojny o ziemie między Bugiem a Wieprzem w XIV wieku przerwały związki ekonomiczne Rusi i Pomorza, co spowodowało regres ekonomiczny Chełma przed nadaniem prawa magdeburskiego.

Akt lokacyjny, przenoszący w 1392 r. Chełm na prawo niemieckie, nie wpłynął na zmianę już istniejącego rozplanowania miasta. Możliwe jest, że wówczas przeprowadzono jedynie niewielką korektę działek budowlanych, a w początku XV w. poszerzono granicę dawnego podgrodzia na zachód i północ. Sto łanów frankońskich nadanych miastu aktem lokacyjnym, był to obszar sięgający od zachodu do Zawadówki, drogi rejowieckiej i Dziewiczej Góry, od północy zajmujący wsie Stańków, Okszów i Nowiny (do późniejszej granicy dóbr Czułczyce), od wschodu graniczący ze wsią Serebryszcze, a od południa z dobrami Uhrowieckimi.

W 1417 r. król Władysław Jagiełło wskrzesił i uposażył diecezję chełmską „upadającą prawie katedrę biskupstwa chełmskiego z ruin podżwignął, kościół katedralny napadami spustoszony oporządził”, a na pamiątkę zwycięstwa swego odniesionego nad zakonem krzyżackim w dzień Rozesłania Świętych Apostołów, tytuł ich nadał w miejsce Ofiarowania Marii.
Dzięki działalności nominowanego na biskupa chełmskiego Jana Biskupca, bliskiego współpracownika króla, diecezja należała do najlepiej zorganizowanych na terenie kraju. Niestety w 1490 r. jej siedziba została przeniesiona do Krasnegostawu.

Chełm po lokacji obejmował górę zamkową (tzw. Górkę) i zachodni stok wzniesienia. Na Górce, na miejscu dawnego grodu chełmskiego, stał posiadający własne umocnienia kompleks zamkowy z katedrą prawosławną i pałacem biskupów prawosławnych. Tędy wiodła droga z Litwy do stolicy kraju. Władysław Jagiełło kilkakrotnie przejeżdżał przez miasto, będące etapem w jego długich podróżach. W 1412 roku droga Władysława na spotkanie z Witoldem prowadziła przez Nowe Miasto-Korczyn, Sandomierz, Pyszów, Sczekarzewice, Lublin, Chełm, Hrubieszów. Trzy lata później wracał Władysław Jagiełło przez Chełm, jadąc wtedy z Łucka przez Włodzimierz, Luboml, Chełm, Krasnystaw do Sandomierza. W tych wszystkich podróżach oparciem dla dworu królewskiego był zamek chełmski. W 1421 r. wracał Jagiełło z Litwy również przez Chełm drogą na Grodno, Ratno, Tur, Luboml, Horodło, Chełm, Krasnystaw.

Miasto oprócz przywileju lokacyjnego otrzymało w ciągu XV i XVI wieku wiele uprawnień handlowych. W 1439 roku miastu nadano prawo odbywania jarmarków w ciągu trzech dni w roku, co wpłynęło na wzrost wymiany handlowej. Oprócz jarmarków odbywały się we wtorki i piątki cotygodniowe targi i codzienny handel detaliczny.

Pewien odsetek ludności, co było specyficzną cechą Chełma, znajdował zatrudnienie przy eksploatacji kredy, wapna i kamienia jako materiału budowlanego. Kreda chełmska cieszyła się wzięciem w całej Polsce, dzięki czemu doszło do powstania pod miastem, istniejącego do dziś, systemu podziemnych korytarzy.