On donne trois explications du nom de Veglie. La première est gréco-byzantine: Elos, le marais. La deuxième est latine: Velio, ou Velia, un nom courant de l'onomastique romaine. La troisième fut avancée par Francesco Ribezzo, et renvoie à une racine prémessapienne, vel, d'origine méditerranéenne, qui signifie hauteur — et c'est la seule des trois qu'on puisse vérifier sur place, car le noyau historique de Veglie se dresse effectivement sur une légère éminence. Le bourg fut fondé vers le dixième siècle, et il s'agit probablement d'une refondation par l'empereur byzantin Nicéphore Phocas après les destructions sarrasines: il fut repeuplé par une petite colonie de Grecs, dont la présence est documentée jusqu'au quatorzième siècle.
Veglie fit partie du comté de Copertino, et son histoire est l'histoire de ces murs. Le premier à tenter de fortifier la Terra Veliarum fut le chevalier français Tristan de Clermont; puis, en 1498, les Castriota Granai refirent l'enceinte et rebâtirent la porte principale, qui pour cela s'appelle Porta Nuova, les travaux étant confiés à l'architecte militaire Evangelista Menga. En 1557 le comté fut acheté par les Squarciafico, une famille de marchands génois. Les armes racontent le reste: il y a une bombarde, choisie au dix-septième siècle par les feudataires comme symbole de force, à laquelle dans la seconde moitié du dix-neuvième on ajouta trois boulets; il y avait aussi une étoile, que le décret de concession n'a pas reprise, et jusqu'en 1943 l'écu était surmonté d'une couronne de marquis, qui renvoyait à un Squarciafico fait marquis de Galatone par le roi d'Espagne. Jusqu'en 1927 Veglie appartenait à la nouvelle province de Brindisi, et cette année-là elle revint à celle de Lecce. Et elle a un hameau abandonné, Monteruga.