В Веррии сохранились остатки церковных построек: баптистерия IV в. и трёхнефной базилики V в. (по мнению исследователей, служившей кафедральным храмом) с мозаичными полами (около церкви св. Патапия), базилики VI в. с мозаичным изображением павлина (ул. Каратасу). Многие византийские храмы были воздвигнуты на развалинах раннехристианских базилик: Старая Митрополия, церковь Сретения Господня (Панагуда), церковь св. Анны и, как полагают исследователи, древнейшая часть церкви св. Стефана. В VII в. равнина вокруг города была заселена славянским племенем драгувитов. В конце VIII в. императрица Ирина отстроила Веррию и назвала её своим именем – Иринуполь, хотя некоторые исследователи относят это известие к Веррии Фракийской (современная Стара-Загора). В 904 г. город был разграблен арабами. В Х в. Веррия входила в Фессалоникийскую фему. Эскуриальский Тактикон (Х в.) упоминает стратига Веррии рядом со стратигом Стримона. В 985 г. Веррия была взята болгарами, царь Самуил поставил правителем города Добромира. В результате болгарских завоеваний Веррия вошла в состав Болгарского патриархата. В конхе алтаря базилики св. Ахиллия, возведённой царём Самуилом в своей столице Преспе, помещены изображения 18 «тронов» (кафедр) Болгарского патриархата, в том числе и Веррийской епархии. В 1001 г. император Василий II Болгаробойца вернул Веррию под власть Византии, но и после завоевания им всего Первого Болгарского царства Веррийская епархия осталась в диоцезе Охридской архиепископии (1018 г.). В Третьем сигиллии (1020 г.) императора Василия II епископу Веррии предписывалось иметь в своём подчинении 30 клириков и 30 париков (зависимых крестьян). В Х–XI вв. в окрестностях Веррии вёл отшельническую жизнь Антоний Новый Веррийский, который считается небесным покровителем города. Впоследствии на месте пещеры, где он подвизался, возник скит Иоанна Предтечи, называемый также Веррийским, т.к. его история неразрывно связана с историей города. В конце XI – начале XII в. была образована особая Веррийская фема. С 1107 г. дукой Веррии был Константин Комнин, племянник императора Алексея I. В письме к нему Охридский архиепископ Феофилакт называет Веррийскую кафедру «одной из прекрасных болгарских Церквей», но говорит о её экономическом упадке. Во второй половине XII в. Веррия вновь была присоединена к Фессалоникийской митрополии Константинопольского патриархата. Исследователи затрудняются определить, взятие какого из одноимённых городов (Веррии Македонской или Веррии Фракийской) было осуществлено в 1186/1187 г. братьями Петром и Иоанном Асенями.