Позицијата на Велес, на главна раскрсница на патиштата на Балканот, Via Ignacia и Via Militaris и многуте други локални комуникациски врски, била интересна за словенското население кое во VI век го поминало Дунав - природната граница на Варварскиот свет и Византија и навлегло длабоко во Балканскиот полуостров. Походите најпрво биле пајонски, а дури потоа кога грото од староседелците (романизирано население од македонско, пајонско и римско потекло) се повлекло кон приморјето и во планинските предели, а словените почнале да ги населуваат. Границата помеѓу антиката и средниот век на тлото на велешкиот регион може да се определи конкретно во 70-тите и почетокот на 80-тите години на VI век. Тогаш се создадени првите склавинии (словенските територии) на територијата на Македонија. Ги зафатиле низиските плодни области покрај Вардар, Тополка и Бабуна при што ги разурнувале градовите и крепостите. Се изменил и етничкиот состав на населението и топонимијата. Тие станале доминантен етнос и по својот говор ги именувале местата. Главниот градски центар тврдината на вливот на реката Тополка во Вардар, тогашна Вила Зора, го добил името Велес.

За името на градот постојат повеќе претпоставки. Една е по густите шуми што ја затворале населбата (шума - лес), друга по богот Волос, трето по името на словенското племе Велегезити. Романизираните староседелци кои биле на повисоко цивилизациско ниво видно влијаеле врз словените учејќи ги како на градежништво, занаетчиство, селско стопанство, така и на својата религија.

Велес припаѓал на склавинијата Верзитија која се протегала помеѓу Велес, Охрид, Битола и Кичево и била населена со Брсјаци. Иако ја признавала Византиската номинална власт, Верзитија се наоѓала надвор од сферата на непосредната управна власт на царството. Она што не и успеало на Византија му успеало на бугарскиот кнез Борис кој во средината на IX век? ја освоил Верзитија. При тоа и велешкиот регион морал да ја признае бугарската врховна власт. Со неа се вратил и подемот на христијанството кое иако не сосем уништено, било во стагнација со доаѓањето на словените.

Воспоставувањето на бугарска власт придонело до интензиривање на процесот на феудализација. Ваквата состојба довела до заострена социјална борба и до појава на широко, антицрковно, антифеудално ослободително движење чии корени се токму на пошироката велешка територија - Богомилското движење. Неговите приврзаници подоцна биле нарекувани Бабуни (според реката Бабуна), а името го добило по основачот попот Богомил. По својата суштина Богомилството е дуалистичко учење за вечната борба меѓу доброто и злото, светлината и темнината, олицетворени во Господ и Сатаната. Ги отфрлале црковните обреди и култови, крстот како симбол, празниците и иконите. Учењето на Богомилите е израз на незадоволство на населението од световната и духовната власт.