Klub Vejle BK założony został 3 maja 1891 jako klub krykietowy. W 1902 początek sekcji piłki nożnej. Do znaczących sił w duńskim futbolu klub należy od lat 50.. Zespół pięciokrotnie zdobywał mistrzostwo Danii i sześciokrotnie sięgał po puchar kraju. W 1991 zespół spadł do 2. ligi. W sezonie 2006/2007 występuje ponownie w Superligaen jako beniaminek.
