Пропаѓањето на Византија го означува почетокот на една долготрајна војна за византиското наследство и најавува најбурни периоди во средновековната историја во велешкиот регион.

На самиот почеток византиската власт во Велес е заменета со бугарска, на чело со царот Калојан. По неговата смрт, великодостојникот Стрез со помош на српскиот жупан Стефан Неманиќ завладеал со голем дел на Македонија. Во составот на Стрезовото независно владеење влегува и Велес. По неговата смрт со велешката област завладеале Латините од Солунското кралство. Во 1219 година Епирците го поразиле Латинското царство и Велес станал нивна територија. Од 1230 година епирската власт била заменета со бугарската. Трговијата што Бугарија ја водела со Дубровчаните има големо значење за велешкиот регион. Но за кратко, од 1246 година владетели во Велес стануваат Никејците. Граничната линија меѓу нив и Епирското царство била на велешкиот регион, по сртот на реката Бабуна, така што повеќе пати Велес бил освојуван те од едните, те од другите, најмногу заради својата стратешка и комуникациска важност.

По обновата на Византиското царство од страна на Никејците, Велес станал значајна гранична област меѓу Византија и Србија.

Од почетокот на XIV век па се до српското освојување во времето на Стефан Дечански, Велес е најистурена византиска тврдина на север. Граѓанската војна во Византија имала директни последици врз велешкиот регион. Одвнатре ослабената Византија неможела да го одбрани Велес и тој во 1328 година потпаднал под српска власт.

Јован Катакузин (Грција) и Јован Оливар (Србија) се сретнале во Велес во 1342 година со намера да склопат Договор за реализирање на дамнешната идеја уништувањето на Византија и создавање Грчко-Српско царство.

Кон средината на XIV век велешкиот регион го владееле Димитрија Волкашин кој го добил заедно со други делови на Македонија, од кралот Душан и деспотот Јован Оливар. По заминувањето на српскиот двор со имотот на Вокашин владеел неговиот син Марко (Крали Марко) кој ги проширил границите на владеење во Македонија. По смртта на татко му, во 1371 година Марко бил прогласен за крал. Но нему не му успеало долго да ги зачува сите територии. Му останала стеснетата држава т.н. Прилепско кралство во кео спаѓал и Велес.

Кон крајот на XIV век Турците започнале голема офанзива на Балканскииот полуостров. Марко ги признал како владетели, но го заштитил населението од директната турска власт. Со неговот загинување по битката кај Ровиње, велешката област била принудена да ја признае трурската власт исто како и целосно Прилепско кралство.


Во XIII и XIV век евидентен е брз растеж на манастирите и манастирските имоти. Оваа појава е поврзана со експанзионистичката политика на Србија која за повеќе од половина век успеала речиси цела Македонија да ја вклучи во составот на српската држава. Во ова време се изградени три големи манастири кои имале свој имот во велешката област. За нив пишува во Грамотите (документи) на манастирите. Цели села од велешката околија со свои цркви и нивниот имот припаѓале на овие манастири (“Св.Ѓорѓи Горг” - Скопски манастир; манастирот Трескавец во Пелагонија и Призренскиот манастир “Св.Архангели”).


На подрачјето на средновековен Велес еведентирани се (до сега) пет сакрални објекти, од кои до денес се сочувани три:

1. Манастирот “Св.Димитрија” кој е сместен источно, во подножјето на ридот на кој е изградена средновековна тврдина или јужно од денешниот град. Архитектурата говори дека датира од XIV век за време на турското владеење е уништен, за да биде повторно обновен кон средината на XIX век од Петар Здравев од Велес.
2. Црвката “Св.Никола” се наоѓа јужно од манастирот на стрмни падини во карпите непосредно под средновековната велешка тврдина. Се смета дека е живописна во почетокот на XIV век, денес е обновена.
3. Црвката “Св.Недела” се наоѓа во северозападниот дел на средновековниот град и нејзината позиција е доминантна. Во турскиот период е уништена, а денес е обновена.
4. Црквата “Св.Архангел” не е лоцирана и идентификувана, а му припаѓала на манастирот “Св.Архангели” од Призрен.
5. Внатре во велешката тврдина на највисоката позиција на акрополата, евидентирани се темели од еднокорабна црква ѕидана со малтер.

Во околината на Велес исто така постојат траги од бројни средновековни сакрални објекти. Еден од позначајните е во клисурата на Бабуна - Пешти, во вертикалната страна на Калето каде е лоцирана Пештерска црква “Св.Марко” од втората половина на XIV век.