La commune apparaît comme mutatio sur la table de Peutinger et celle d'Antonin. Elle est confirmée dans ce rôle sur l'Itinerarium Burdigalense seu Hierosolymitanum - Itinéraire de Bordeaux à Jérusalem daté de 333 après JC - Une mutatio est l'équivalent de nos relais-routiers le long des voies romaines et médiévales. Le voyageur peut s'y restaurer, y coucher et y changer son cheval. Elles s'espacent tous les 15 à 20 km.
Veynes apparaît en 1100, sous la forme Venettum, Vehenetum en 1135 et Vedenez en 1140, pour passer à Veene en 1150. Sa forme semble se figer en Veyne dès 1516. Certains toponymistes ont vu dans le radical Ven le sens celtique de pierre, rocher, hauteur. Un comparatif avec le breton, langue celtique, peut être constructif.
Suivant le genre et le nombre, cette langue peut présenter une mutation de la consonne initiale. Dans ce schéma, la consonne M s'adoucit en V. Nous remarquerons aussi que pierre se dit Maen et pierreux - Maeneg. Ces remarques nous rapprocheraient du Venet-tum de l'an mil et confirmeraient le sens de ce radical Ven.
Le pierrier du pic de Bure, le plus grand d'Europe semble lointain - 30km - bien que remarquable. Peut-être quelques roches ou éboulis assez significatifs et maintenant disparus ont-ils imposé ce toponyme.
