Troldhede - Kolding - Vejen jernbane TKVJ var et resultat af mange planer for en jernbane i området nordvest for Kolding. Disse kolliderede ofte med planer om en jernbane vest for Vejle (VVJ) og en forlængelse af denne til Esbjerg eller et punkt på jernbanen mellem Esbjerg og Tarm.
Lige før århundredeskiftet var der planer om en jernbane fra Lunderskov til Vorbasse. Men først med Den Store Jernbanelov i 1908 blev planerne konkrete. Banen Kolding-Gesten-Grindsted-Sdr.Omme-Troldhede med sidebanen Gesten-Vejen.