Men tyskerne var også i området i begyndelsen af 1600-tallet, hvor Chr. 4. med meget ringe succes havde blandet sig i 30-årskrigen.
Resultatet af den danske konges indblanding blev bl.a., at Jylland kom til at ligge åben for Wallensteins hærgende tropper. Helt op til Vendsyssel nåede de, og bl.a. ved Fladstrand byggede oberstløjtnant von Hatzfeldt en skanse ved kysten for at forhindre dansk landgang. Skansen ligger der stadig og kaldes i dag Nordre Skanse.
Heller ikke mod svenskerne havde Chr. 4. held i den militære sprøjte. Ved en fredsslutning i 1645 måtte han afstå dele af de danske besiddelser i Sverige, og Chr. 4.s efterfølger Frederik den 3. fuldendte fiaskoen i 1658, hvor Skåne, Blekinge og Bohuslen efter Roskildefreden blev svensk.
Nu stod danskerne med et problem. Norge var stadig en del af riget, og Norge kunne ikke brødføde sig selv. Derfor skulle der sejles masser af korn op til nordmændene, og sejladsen plejede at foregå langs den svenske kyst. Denne sejlrute kunne nu ikke længere benyttes, og der skulle nytænkning til hos admiralerne i København.
Den første nytænkning bar præg af at være produceret ved en skrivepult: Sejladsen skulle nu lægges op langs den jyske østkyst, og som støttepunkt for sejladsen skulle der bygges en fæstning ved Hals. At sejladsen skulle lægges østover var indlysende, men det var placeringen af et støttepunkt ved Hals ikke.
I hvert fald ikke, hvis man spurgte de søfolk, der skulle føre nytænkningen ud i livet. For en sømand ved sine fulde fem ville da ikke sejle ind til Hals, hvis der blev behov for beskyttelse mod vind og vejr. Han ville lægge sig ind under Fladstrand. Efter denne tilbagemelding fra virkeligheden blev fæstningen bygget i Fladstrand.
Fæstningen blev opført syd for den gruppe af huse, der i dag kendes som Fiskerklyngen, og som i 1680'erne udgjorde Fladstrand. Fæstningen bestod af 2 dele: Citadellet, der med sit svære tårn stod som en knytnæve ud mod havet, og det bagvedliggende hornværk, der skulle beskytte citadellet mod angreb fra land.
Hornværket var omgivet af volde, indenfor hvilke der blev placeret bygninger til
kommandantskabet, mandskab, proviant og forskelligt udstyr. Den oprindelige kommandantbygning er nu væk, men dens efterfølger kan i dag ses ved siden af Frederikshavn kirke.
Citadeltårnet er blevet bevaret, om end det ikke står på sin gamle plads. Det blev bygget med etageadskillelse i træ, men det var forberedt til en senere indbygning af hvælvinger, hvilket skete under kanonbådskrigen 1807-14.
Tårnet kaldes i dag "krudttårnet", og selvom der uden tvivl også blev opbevaret krudt i tårnet, har det som hovedfunktion haft at være platform for kanoner. Fladstrand Fæstning fik stor betydning som base for kanonbåde i krigen mod England 1807-14, men også under Store Nordiske Krig 1700-1720 spillede fæstningen en stor rolle som Tordenskiolds eneste base udenfor København.