Den nuværende station er den anden banegård i Fredericia. Den blev anlagt samtidig med den gamle Lillebæltsbro og åbnede i 1935. Stationen erstattede den gamle rebroussementsstation ved havnen, hvorfra der hidtil havde været videre forbindelse til Fyn via jernbanefærge til Strib.
Den første station i Fredericia var en rebroussementsstation beliggende tæt ved havnen, så der nemt kunne opnås forbindelse til og fra Fyn og Sjælland via jernbanefærgen fra Fredericia til Strib. I første omgang blev der i 1866 opført en provisorisk stationsbygning af træ, der senere blev flyttet til Nørresundby. Den egentlige stationsbygning stod færdig i 1869. Den gamle stationsbygning eksisterer stadig på adressen Oldenborggade 1 og er i dag indrettet til kontorer.[7]
Den nuværende station i funktionalistisk stil med et islæt af klassicisme er tegnet af arkitektenKnud Tanggaard Seest, der var overarkitekt ved DSB fra 1922 til 1949.[2] Stationen har en banegårdshal, hvilket er ualmindeligt i Skandinavien. Faktisk er banegården én af blot fem i Danmark med banegårdshal; de øvrige er Københavns og Aarhus Hovedbanegård, Nørrebro S-togsstation, samt den nu nedlagte Gedser Station. Desuden har stationen Danmarks længste perroner, som er hver 330 meter lange. Dette hænger sammen med at Fredericia er et vigtigt trafikknudepunkt for DSB, hvor stadig mange passagerer skal skifte tog under deres rejse og at de fleste intercity- og lyntog fra København bliver splittet op og kører til de andre forskellige byer i Jylland. Omvendt bliver togene fra de forskellige byer samlet, når de er på vej til København.