Во периодот на раната антика, територијата на Велес влегувала во составот на Пајонската држава, која се претпоставува ја сочинувале голем број градски населби.

Хелинистичкиот слој јужно од градот кај локалитетот Кале при влезот во Велешката клисура покрива плато од 3,5 ха површина оградена со бедем, на кое бил лоциран најголемиот Пајонски град Вила Зора (Била Зора). Вила Зора имала положба на самиот влез на Дарданија во Македонија (Пајонија) така што Филип V освојувајќи ја во 217 година пред н.е., ја обезбедил својата држава од упадот на Дарданците. Вила Зора како значаен воен центар се до последните години на Македонското владеење, се спомнува последен пат во 168 година пред н.е.

Континуитетот на името Вила Зора и Велес тешко може да се одреди, зошто Велес се спомнува дури во 1018 година. Се претпоставува дека во оваа временска празнина моќта на Вила Зора во римското владеење опаднала или пак нејзината локација треба да се бара на друго место.
Во пошироката околина на Велес има повеќе траги кои укажуваат на античкиот град Аргос поврзан со територијата на Macedonija sekunda.