Первое упоминание о Велешине (точнее, о пане Велешина) содержится в грамоте, выданной 26 июня1266 года, в которой говорится о том, что Чеч из Велешина (Чеч из Будеёвиц), владелец замка Велешин, вместе со своей женой Гизелой фон Куенринг даровали некие земельные имения Цветльскому аббатствуШаблон:Sfn.
Селение Велешин было основано в XIII веке в связи со строительством королём Пршемыслом Отакаром I или Вацлавом I в первой трети XIII века королевского замка на мысе над рекой Малше. Поселение Велешин возникло на противоположной стороне реки. Король Пршемысл Отакар II в 1265 году передал замок и селение Велешин Чечу из Будеёвиц в обмен на земли вокруг основанного королём города Ческе-Будеёвице. Чеч из Будеёвиц продал Велешин Бенешу Гордому из рода Марквартовичей, который после этого принял предикат «из Велешина». В скором времени король Пршемысл Отакар II изъял замок и селение Велешин в королевское владение, однако 28 августа 1283 года король Вацлав II вернул Велешинское панство Яну I из Михаловиц, сыну Бенеша ГордогоШаблон:Sfn.
В 1387 году Ян IV из Михаловиц продал разросшееся Велешинское панство Ольдржиху I из Рожмберка, во владении потомков которого Велешин находился до 1611 года. При панах из Рожмберка статус Велешина был повышен до местечка с правом устраивать рынки; в этот же период начал использоваться городской герб ВелешинаШаблон:Sfn.
В городе находится совместное предприятие JIHOSTROJ Велешин, известный производитель гидравлических устройств и систем управления для авиационной и автомобильной промышленности, основной акционер JAWA Moto spol. s r.o. (знаменитой фирмы, производящей мотоциклы «ЯВА»).
