Drømmen om en fast Storebæltsforbindelse går tilbage til 1858, hvor tidligere krigsminister A.F. Tscherning af militære grunde foreslog Rigsrådet, at der skulle bygges jernbanetunneler under Lillebælt og Storebælt, og i 1934 blev der udarbejdet et forslag til en vej- og jernbanebro mellem Halsskov og Knudshoved.
I 1936 blev der af tre ingeniørfirmaer fremsat et færdigt forslag til broer over Storebælt (og Øresund) som led i et landsdækkende dansk motorvejsnet. Året efter den strenge isvinter i 1947 blev der nedsat en kommission, der arbejdede til december 1959. I betænkningen fra 1960 blev det anført, at fortsat færgedrift ville kræve 12 todæksfærger i fart i 1980. Kommissionen anbefalede derfor at bygge en tog og motorvejsbro over Storebælt, og der nedsattes derpå et udvalg, som frem til november 1968 arbejdede videre med forslaget.
Trafikudviklingen betød dog, at man fortsat måtte udbygge færgedriften. I 1973 blev en ny tredæksfærge, Romsø, og den første intercityfærge, Dronning Margrethe II, sat i fart. Samtidig vedtog Folketinget at anlægge en fast tog- og motorvejsforbindelse over Storebælt, og til at projektere forbindelsen, stå som bygherre og senere til at varetage driften af broen oprettede staten organisationen Statsbroen Store Bælt. Broen skulle være færdigbygget i 1982. Projekteringen kom hurtigt i gang, men pga. oliekrisen i 1973 og den efterfølgende økonomiske afmatning blev planerne om Storebæltsforbindelsen sat i bero i 1978. Året efter kom den næste oliekrise, hvilket atter udsatte planerne om en fast forbindelse.
Overfarten blev fortsat udbygget. I 1974 indførte DSB timedrift med intercitytog på hovedbanerne mellem København og de største jyske byer, og samtidig indsattes intercityfærgen Prins Henrik på Storebælt. I 1980 blev de to firsporede intercityfærger Dronning Ingrid og Prins Joachim sat i fart, og i 1981 fulgte søsterfærgen Kronprins Frederik. En privat bilfærgerute, Vognmandsruten, mellem Korsør og Nyborg blev oprettet i 1984, og fra 1987 blev den kraftigt udbygget.