Веднаш по паѓањето под турска власт (1395 година) Велес подпаднал под управата на Румелискиот беглербеглак. До 60-тите години на XIV век областа го носела името велешки вилает, а потоа Велешка нахија како најниска управно територијална единица. На чело на вилаетот се наоѓал субашија кој живеел во Велес и заповедал со спахиите кои по правило живееле во селата. Паралелно со ова Велес станал центар на велешката каза или кадилак со што прераснал во многу значајна управно - судска единица.

Со навлегувањето на Турците, голем дел од месното население, особено влашко-сточарското, ја напуштило областа. На нивно место се доселило турско, пред се јуручко-сточарско население. На тој начин се добиле извесен број нови, чисто турски населби лоцирани од левата страна на р.Вардар. Кон ова се надоврзувало и постојаното исламизирање на дел од покореното население. Такви демографски промени се почуствувале и во градот кој почнал да добива белези на турската цивилизација.

Од тогашниот попис на населението (1445 година) сеуште има показатели дека велешкото Кале е населено. Затоа со сигурност не може да се определи дали градот се наоѓал на сегашното место во време на доаѓањето на Турците (1395 година) или нивното лоцирање на сегашната градска територија го провоцирало мигрирањето на старото население. Во пописот 20 години подоцна старата градска тврдина веќе не е населена. Просторот крај Калето не бил доволен за еден управно-административен центар каков што почнува да станува Велес во ова време. И тврдината и населбата го добиле името Ќупрулу (место со мост или мостово, подоцна град со мостови). Во средината на XVI век во неги живееле 214 христијански и 35 муслимански семејства. Социјалната и професионалната структура на населението била обратна од етничката. На горните општествени скалила било турското, а на дното македонската градска сиромаштија. Меѓу нив се наоѓал најбројниот слој на средно-имотни граѓани од двата етноса.