Med den valgte placering af Lillebæltsbroen måtte DSB bygge helt nye baneføringer frem til brohovederne på begge sider af broen. Samtidig valgte man at bygge helt nye banegårde i såvel Fredericia som i Middelfart.
Fredericia banegård lå nede ved havnen – tæt på færgelejerne. Nu valgte man at lægge den nye banegård uden for voldene, så man fik plads til det væsentlige jernbaneknudepunkt, som Fredericia kom til at blive.
Baneforlægningen på den jyske side blev da også det mest omfattende: Den startede ved brohovedet i Snoghøj og var 12 km lang. Den nye banegård med rangerspor, personvognsdepot, lokomotivdepot, godsbanegård fyldte 70 ha, og mellem de yderste sporskifter i nord og syd er der 5,6 km. Banegården fik 7 perronspor, 300 meter lange. Beskæftigelsesmæssigt var det langt den største opgave i hele brobyggeriet, hvor der var ansat op til 500 arbejdere. Ca. 60 % var Statsbanernes egne anlægsfolk. Herudover kom de mange, som var beskæftiget med leverancer fra underentreprenørerne. Der var 230 entrepriser på den jyske side.
Den fynske side var mere begrænset i omfang: Baneføringen til Strib blev bevaret, men hovedlinien med en forlægning på 4,3 km kom til at gå direkte mod brohovedet, og den nye banegård blev placeret midt på den nye strækning, tæt ved Middelfarts centrum.
Men samtidig skulle Nordvestfynske Jernbaner (Middelfart-Brenderup-Odense/Bogense) føres ind til den nye banegård i lighed med det vigtige spor til Middelfart Havn og Nordisk Kabel- og Traads Trådværk. Alt i alt betød dette flere gennembrud gennem eksisterende parcelhuskvarterer i byens østlige ende.
Hertil kom så de nye færdselsveje, da det blev besluttet at bygge vejbaner på broen.
På den jyske side var der ikke de store problemer. Den gamle landevej til Kolding og Vejle blev udbygget, og der kom en ny direkte vej ind til Fredericia. Middelfart ønskede tilsvarende at bruge den gamle landevej - dvs. ind gennem byens hovedgade. Byen kæmpede bravt for denne linieføring, men forgæves. I stedet valgte man at lægge vejen syd for banen. Derved fik Middelfart uden at ville det en omfartsvej uden om den gamle købstad. Men byen blev skåret over. Alle nord-sydgående veje måtte enten føres over eller under jernbanen, eller, som det blev for et par af de mindre veje, simpelthen lukkes.
De samlede udgifter til bro- og jernbanebyggeriet blev på 42 mio. kr. Heraf kostede jernbanebroen 16,7 mio. kr., færdselsbroen 7,5 mio. kr., vejanlæggene 1,6 mio. kr. og de tilsluttende jernbaneanlæg 16,5 mio. kr. De mange arbejder på og omkring Fredericia Banegård kostede alene 11 mio. kr.
