Duński klub założony w 1891 roku, zdobywca krajowych dubletów w 1958 i 1972 roku.
Vejle Stadion znajduje się przy Roms Hule 6. Pierwszy mecz na nowym obiekcie rozegrano 9 marca 2008 roku: Vejle przegrało z FC Midtjylland w ćwierćfinale Pucharu Danii. Oficjalna inauguracja stadionu odbyła się 20 marca tego samego roku.
Osobnym zapleczem jest VB Parken, kompleks boisk z klubowym budynkiem i szatniami.
Początkowo piłkarze grali w niebieskich koszulkach, o ile udało się zgromadzić ich wystarczającą liczbę. Czerwone koszulki stały się oficjalne w 1911 roku; w nich zespół zdobył mistrzostwo Jutlandii w rozgrywkach 1911/12.
Vejle Boldklub powstało 3 maja 1891 roku. W 1913 dołączył Carl Maibom, doświadczony zawodnik OB i B93, który po pierwszym występie przeciwko Grindsted chciał odejść: sprzeciwiał się bójkom z rywalami i między kolegami z drużyny. Piłkarze, działacze i członkowie zarządu przekonali go do pozostania, a Maibom został grającym trenerem bez wynagrodzenia, odpowiedzialnym także za zachowanie zespołu. Vejle zdobyło mistrzostwo Jutlandii w 1913 i 1914 roku.
Pierwsze mistrzostwo Danii i krajowy puchar klub zdobył w 1958 roku; drugi dublet wywalczył w 1972. W 1978 został pierwszym mistrzem Danii po dopuszczeniu profesjonalnej piłki przez DBU. Pierwszym zawodnikiem zatrudnionym na kontrakcie był Alex Nielsen, który spędził w Vejle kolejne dziesięć lat i zdobył z nim dwa mistrzostwa kraju. W tym samym 1978 roku drużyna dotarła do ćwierćfinału Pucharu Zdobywców Pucharów, gdzie odpadła z FC Twente.
W 1988 nowe inwestycje umożliwiły sprowadzenie Prebena Elkjæra. Jego debiut 21 sierpnia przeciwko OB obejrzało 14 800 widzów, a spotkanie zakończyło się remisem 2:2. Mimo tego transferu Vejle zajęło piąte miejsce w lidze.
W 2008 roku Vejle wygrało rozgrywki drugiego szczebla i awansowało do SAS Ligaen. Rozwój młodzieży wspiera współpraca z lokalnymi klubami pod nazwą Future Vejle.
Spotkania z AGF są historycznym klasykiem Jutlandii. Pierwszy mecz tych klubów w 1940 roku zakończył się remisem 1:1, a rywalizacja nabrała znaczenia w latach pięćdziesiątych, gdy oba zespoły zaczęły zdobywać krajowe trofea i przełamywać dominację klubów z Kopenhagi.
