Indtil 1650 var der urørt sump, hvor Fredericia by ligger i dag. Ved første øjekast måske ikke et oplagt sted at etablere en by. Men kongen havde brug for en strategisk velplaceret fæstning, og i forhold til både land og vand var Bersodde, som området hed, ideelt.
Med en kystlinje til to sider, kunne man med relativt få kilometers voldanlæg, befæste og beskytte byen og samtidig kunne forsyninger og tropper fragtes ind og ud af byen fra søsiden.

Over 5000 mand deltog i opførelsen af voldanlægget. Arbejdet foregik naturligvis med håndkraft og strakte sig over en årrække. Inden man nåede at færdiggøre det, kom en ny krig mod svenskerne imidlertid på tværs – med forsinkelser og ødelæggelser af Volden til følge.

En by uden indbyggere

For at skaffe indbyggere til den nye fæstningsby, overvejede man at tvangsflytte alle Vejles borgere. I stedet nøjedes kongen med at flytte indbyggerne fra de nærliggende landsbyer Hyby, Hannerup og Ullerup ind bag voldene. De fleste var agerbrugere og det var mildt sagt ikke populært, at de nu skulle bo i byen indenfor voldene og dyrke deres marker udenfor voldene. Men kongen fik naturligvis sin vilje.

For at tiltrække folk udefra indførtes en række kongelige privilegier som gjaldt særligt for Fredericia. Det var blandt andet skattefrihed, gratis byggegrunde, straffrihed for kriminelle, asylret, toldfrihed og religionsfrihed – noget man ellers ikke havde dengang. Nyheden om religionsfriheden i Fredericia spredte sig ned gennem Europa og tiltrak bl.a. jøder, franske huguenotter (De Reformerte) og katolikker. Fredericia blev derfor en kulturel smeltedigel og nød godt af tilflytternes medbragte afgrøder som tobaksplanter, kartofler og hvede.