Среден Век

По византиското освојување на Скопје, околината на Велес повторно станала гранична територија на македонската држава, каква што била и во антиката. Во пишаните извори од ова време, Велес се спомнува неколкупати. Во повелбата на Василиј ИИ од 1019 г., Велес е спомнат како еноријско седиште под јурисдикција на епископот на Пелагонија (Битола); зачуван е и еден детален опис на борбите на никејскиот цар Теодор ИИ Ласкарис, кој во 1255 г. го вратил Велес под своја власт и го принудил екипажот од 500 луѓе да му се предадат. Во 1330 г., по битката кај Велбужд, Србија ги добила пограничните византиски тврдини Велес, Чрешче и Просек. Бидејќи границата сега се поместила далеку на југ, Велес го загубил дотогашното воено стратешко значење, а во старите бедеми продолжило да живурка цивилното гратче Велес.