Vejle perustettiin 1100-luvulla saarelle, jokilaakson suistoon. Ensimmäinen maininta kaupungista on vuodelta 1256. Yhdyskunnalle myönnettiin kaupunkioikeudet vuonna 1372, mutta vasta 1800-luvun puolivälissä teollistuminen myötä Vejle muotoutui nykypäivän suosituksi ja varakkaaksi alueensa pääkaupungiksi.lähde?
Kulttuuri
Nähtävyydet
Kaupungissa on kukoistavia kävelykatuja ja historiallisia rakennuksia. Kulttuuria Vejlessä tarjoavat konserttihalli, musiikkitetteri ja kansainvälinen Casino Munkebjerg. Lisäksi kaupungissa pidetään erilaisia kulttuuritapahtumia. Vejlessä on myös useita museoita, muun muassa hiljattainmilloin? uudistettu Vejlen taidemuseo, joka sisältää merkittäviä kokoelmia Tanskan ja Euroopan kuvataiteesta, ja Økolariet, joka on käytännön oppimiskeskus luonnosta, ympäristöstä ja sähköntuotannosta.
Muita nähtävyyksiä ovat muun muassa Vejlen vanhin rakennus Pyhän Nikolain kirkko 1200-luvulta, ja kaupungin maamerkkinä toimiva tuulimylly vuodelta 1847.