Со освојувањето на Скопје од страна на Византија, во 1004 година, велешката област станала гранична територија на македонската држава и добила улога на заштитник на нејзините цетрални делови. Царот Самоил се обидувал да го запре Византиското навлегување, но во битката на Беласица во 1014 година доживеал катастрофален пораз. Со освојувањето на Прилеп и Штип, Велес останал отсечен од Македонија. Успевал да опстои само до 1018 година кога за прв пат од доаѓањето на Словените бил принуден да потпадне под директна византиска власт т.е. да стане дел на византиското царство.

Воено-административно Велес во Византиското владеење припаѓал на темата Бугарија, но начинот на живот, даноците и религиската припадност останалене непроменети. Велес сеуште бил дел на Битолската епархија во составот на Охридската патријаршија на која и е одземен рангот