Byen Veles voksede i det19. århundrede og blev til et vigtigt handelscenter. Da Makedonien var en del afJugoslavien, var byens navn Titov Veles (en af fire byer i Jugoslavien som havde Titos navn), til ære for den jugoslaviskepræsidentJosip Broz Tito (1893 –1980).
Omkring 20 km syd for Veles, tæt vedKumanovo –Gevgelija motorvejen (eller på den gamle hovedvej 1 til Gevgelija) ligger ruinerne af den gamle byStobi, som stammer helt fra år197 f.Kr. Byen var på den tid hovedstad i den makedonske romerske provinsSalutaris.
