Пошироката околина на денешен Велес била населена уште во праисторијата. Докази за човечко присуство се најдени во пештерата Макаровец во месноста Пешти, каде што се вршени единствените темелни истражувања на палеолитот во Македонија, а се пронајдени фосилни фауна и артефакти од камен, веројатно од доцниот палеолит. Во античко време, територијата на денешен Велес влегувала во македонската област Амфакситида, која се протегала по бреговите на реката Аксиј (Вардар) а областа била населена со македонски племиња од пајонско- пелагонската група. Траги од населби се најдени на локалитетот Теќе, на 2 километра од Башино Село, како и во месноста Тумба во село Караслари; антички некрополи има во селата Иванковци и Долно Оризари. Постојат неколку сведоштва за античкиот град Аргос, кој се наоѓал во близина. Местоположбата на Велес ќе добие поголемо значење на преминот од антиката во средниот век.