Frederik den 3 gav i 1649 ordre om der skulle projekteres en Fæstning ved Lillebælt. Frederiksodde blev valgt efter at der var prøvet flere andre lokationer i området omkring Lillebælts smalleste sted. I 1664 blev navnet ændret til Fredericia.
Det var en grundtanke at en fæstning ikke kunne stå alene, det måtte samtidig være en by med handel, landbrug og søfart. Der blev også projekteret et slot omkranset af kanaler, i tilfælde af at kongen valgte byen som residens hovedstad.
Fredericia blev projekteret stort uden et skelen til praktiske vanskeligheder. Området var dengang, for en stor dels vedkommende, mose og sump. Så uagtet at der blev lovet skattefrihed og udloddet gratis jordlodder, var det vanskeligt at befolke byen. Derfor blev landsbyerne, Hyby, Hannerup og Ullerup tvangsnedlagt. Gårdene brudt ned og bygget op igen indenfor voldene, og bønderne blev tvangs forflyttet indenfor voldene i Fredericia.
Selve Voldanlægget og Bastionerne ved Fredericia blev igangsat i 1650. Arbejdet blev udført af 5.000 soldater og fæstebønder, Det har været et kæmpe arbejde, der har krævet mange kræfter, da der udelukkende blev anvendt hjulbører, hakker og spader.