Deși a fost reparat de împărații Licinius, Iulian Apostatul și Valens, orașul va suferi distrugeri mari în timpul migrațiilor din secolele V-VI (este menționată și o mare inundație provocată de un tsunami în secolul al VI-lea) și va decădea treptat. Au trecut succesiv prin zonă goții, ostrogoții, antii, slavii, bulgarii, gepizii, cutrigurii, avarii. Dintre toți, slavii au avut cea mai mare influență, stabilindu-se în număr mai mare la sud de Dunăre, mai ales la începutul secolului al VII-lea, secol în care provincia va fi reorganizată de împăratul Constantin al IV-lea în „Thema Scythia„.
Curând după această însă, hanatul bulgar al lui Asparuh, ajuns la nord de Dunare în urma luptelor cu khazarii, câștigă în anul 680 războiul cu Imperiul Bizantin și cucerește Dobrogea și Moesia. Un an mai târziu hanatul este recunoscut ca stat independent (Primul Țarat Bulgar), dar bizantinii și-au păstrat controlul încă 3 secole asupra țărmului Mării Negre, cu intermitențe și asupra zonei vechii cetăți Dionysopolis. Aceasta, dacă nu dispăruse, oricum nu mai avea caracter urban, decăzând și datorită dezvoltării cetății vecine Varna. Reconstrucția ei s-a făcut cu aportul din ce în ce mai mare al proto-bulgarilor, sus pe podișul ce domina vechea așezare (loc unde se mai păstrează vestigii ale așezării medievale din secolele IX-XIV). În anul 895, prin Dobrogea au trecut și triburile maghiare, venind din Bugeac, iar în secolul următor sunt menționați primii stăpânitori feudali locali, probabil de origine slavă („Jupan Dimitri” în sudul Dobrogei).
Cu sprijinul împăratului bizantin Nichiphor al II-lea Phokas, cneazul Sviatoslav I al Kievului atacă Țaratul Bulgar și ocupă Dobrogea în anul 968, mutând capitala Rusiei Kievene pentru 3 ani la gurile Dunării. În 971 însă, împăratul Ioan I Tzimiskes îl invinge pe Sviatoslav și îl alungă din Tracia și Dobrogea, restabilind în zonă autoritatea bizantină. Odată cu apogeul Primului Țarat Bulgar, sudul Dobrogei va fi anexat acestuia de către țarul Samuil, care în prima fază l-a învins pe împăratul Vasile al II-lea Bulgaroctonul; acesta revine în anul1000 și distruge complet până în 1018 Țaratul Bulgar, organizând în Dobrogea „Strategia Dorostolon” și apoi „Thema Paristrion / Paradunavon„.
Stăpânit de bizantini întreg secolul al XI-lea, țărmul sudic al Dobrogei va fi cunoscut și el, ca întreaga regiune, invaziile pecenegilor, uzilor și cumanilor; în aceeași perioadă sunt menționați în zonă și lideri locali, precum Tatrys/Tatos, Sestlav și Satza (probabil pecenegi) sau Pudilă (vlah). Începând cu secolul XII, dominația cumanilor s-a accentuat, iar după înfrângerea acestora din anii 1122-1123 de către împăratul Ioan al II-lea Comnenul, asimilarea lor de către băștinașii vlahi va duce la apariția elementului etnic românesc la Dunărea de Jos, coabitant cu cel slavo-bulgar. Aceste două principale populații autohtone, împreună cu resturile cumanilor, au participat în 1185-1186 la răscoala Asăneștilor.
Dobrogea va rămâne în granițele imperiale până la începutul secolului al XIII-lea, când, în contextul înlocuirii Imperiului Bizantin cu cel Latin de Răsărit, va intra sub autoritatea Imperiului Vlaho-Bulgar al Asăneștilor (Al Doilea Țarat Bulgar).
În 1241 coloana sudică a marii armate mongole, sub conducerea lui Kadan, a invadat și Dobrogea, în drumul său spre vest. Autoritatea Asăneștilor a fost slăbită, și drept consecință, Hoarda de Aur și-a extins stăpânirea și asupra Dobrogei; de atunci a început colonizarea zonei cu turci selgiucizi și tătari islamizați (parte din urmașii acestora, trăind printre creștini, au devenit găgăuzii de mai tarziu). Tot în această perioadă, datorită vremurilor nesigure, orașul s-a mutat din nou spre mare, în locuri mai greu accesibile – înălțimile apărate natural (în special dealul mare, numit Djinna Bair, unde s-au descoperit vestigii ale construcțiilor din secolele XIII – XIV).
