Der har boet mennesker i området omkring Frederikshavn siden stenalderen. Ved Gærum ligger en af Danmarks største og smukkeste langdysser samt Vendsyssels eneste og en af Danmarks største og smukkeste jættestuer. Ved Donbæk er der fundet en gravplads, der har være benyttet gennem hele jernalderen. Ved Lygten, Bækman og Donbæk er der fundet adskillige og stadig uforklarede kældre fra jernalderen.

I Hørkær mose er der fundet et stort depot- eller offerfund fra stenalderen med flot forarbejdede økser, knive og dolke. Indenfor de seneste år er der fundet et tragtbæger ved fiskeri i Kattegat, og de mange fund af uforarbejdede flintestykker i Sverige kunne tyde på en tidlig eksport af flint fra minerne i Nordjylland til Bohuslen.

Det er ikke til at sige, hvornår Fladstrand, som Frederikshavn hed før 1818, opstod. Første gang byen dukker op i kilderne er to år før reformationen i 1536. Det er som så ofte siden, en klagesang fra byens skipperkøbmænd, som føler at de ikke har de samme betingelser som købmænd i Købstæderne.

Alt tyder på, at vikingetidens og middelalderens vigtigste bysamfund lå ved Elling Ås udmunding i den naturhavn, hvor Ellingåskibet blev udgravet i 1968. Her blev Elling kirke også opført ganske tæt ved naturhavnen, og den gamle Gyldenstjernegård Ellinggård. Materialevandringer, landhævning og større dybdegang på skibene har betydet, at området ikke længere kunne bruges. I 1466 oprettedes herregården Lerbæk på det fine marskområde, som dannedes, hvor naturhavnen lå. Her gik adelens vigtigste indtægtskilde øksnene rundt og græssede.

Det var derfor vigtigt at finde en ny havn, der ikke var så sårbar, og som kunne bruges af de stadigt større skibe, som passerede forbi området.

Det vikingerne havde gjort til en lukrativ forretning, fortsatte, selvom vikingetiden ophørte. Mare Baltikum, eller Østersøen, forblev en vigtig handelsvej mellem øst og vest. En handelsvej, som den danske konge forsøgte at holde for sig selv i konkurrence med først Hansestæderne, dernæst de Nederlandske købmænd, englænderne og ikke mindst Sverige.

Omkring 1600 var handelen over byen blevet så betydningsfuld, så Chr. IV bad sin tolder i Sæby om at interessere sig for, hvor mange varer der flød ud og ind. Både de varer som adelen, på grund af deres privilegier frit kunne handle med, og ikke mindst smugleriet. En af kongens vigtigste indtægtskilder var toldafgifter, som på denne måde blev udeholdt fra kongens kasse, som skulle føre Danmark og ikke mindst kongen ind på en førerposition, som Nordeuropas vigtigste protestantiske fyrstehus.

Det lykkedes som bekendt ikke. I stedet blev Jylland besat fra 1627-29 af de katolske kejserlige tropper, som byggede den første skanse ved Fladstrand. Op gennem 1600-tallet mistede kongen magten over hele kysten fra Blekinge over Halland og til Bohus len, og Fladstrand blev efterhånden det vigtigste hængsel i et forsøg på at få tvillingerigerne Danmark og Norge til at hænge sammen.

De mange krige, og besættelser af Danmark op gennem 1600 tallet betød en vældig udvikling for Fladstrand. Det lille fiskerleje voksede og kirken måtte udvides flere gange. I 1669 var byens betydning vokset så meget, at det Kongelige Toldsted flyttedes fra Sæby til Fladstrand, og samtidig indførtes der konsumptionstold, som i landets købstæder. Byens købmandsborgerskab blev dermed pålagt yderligere forpligtigelser uden at få noget til gengæld. Først i 1748 gjorde en enkelt købmand noget ved det. Han købte simpelthen hele byen med dens huse, jord og næsten også dens indbyggere.

Op til 1690 udvidedes Søndre skanse til en egentlig fæstning. Et hornværk, med et Martellokrudttårn, som stadig er byens vartegn. Desuden befæstedes den lille ø Deget, så byens havnered var beskyttet fra tre skanseanlæg. Desuden fik indbyggerne deres egen kirke, så de ikke længere skulle gå den lange vej til Flade kirke.

Der var lagt op til noget stort, og det skete da den danske konge indledte et angreb fra Norge ind i Bohuslen, for at erobre den nye svenske storby Göteborg. Felttoget blev en katastrofe. Kongen havde glemt at soldaterne skulle have forsyninger under felttoget. Den svenske flåde var blevet så stærk at den kunne operere frit i Kattegat og fange de danske transportskibe. Først med organiseringen af den dansk norske flåde med Tordenskjold i spidsen for en konvojtjeneste, lykkedes det at forsyne hæren, så den i det mindste ikke led nederlag. Desuden havde Tordenskjold held til at erobre den gamle Danske fæstning i Marstrand, mens et dristigt forsøg på at angribe Göteborg slog fejl.

Efter Store Nordiske krig gik udviklingen ikke længere så hastigt for byen. Den manglede en egentlig havn, og indbyggerne begyndte at presse på for at få sat udviklingen i gang igen. Stadigt flere og større skibe passerede byen, der lå på den kæmpe havmotorvej, som forsynede England med brødkorn. Den engelske industrialisering var gået i gang, og englænderne kunne aftage alt det som Danskerne, Polakkerne, og Balterne kunne producere, og Frederikshavn lå strategisk placeret ved det farligste sving på vejen til England.

Efter 80 års fred rumlede krigstrommerne igen. Denne gang var det England og Frankrig der kom op og toppes om hvem der skulle bestemme i Europa, og hvem der havde ret til kolonier i den nye verden, som indianernes Amerika blev kaldt. Det gik ellers lige så godt. Danske købmænd tjente penge hjem til landet ved at hente varer i kolonierne og sælge dem til englænderne, tyskere og franskmænd. Det kunne de ikke lide i England, og derfor besluttede kongen at han ville beskytte handelsskibene ved at lade dem sejle sammen med orlogsskibe. Dermed kastede englænderne os lige i armene på Napoleon.

Englandskrigen fik store konsekvenser for Danmark og Fladstrand. Endnu engang var det en krig der pustede liv i byen. Allerede inden den engelske flåde bortførte den danske flåde og med verdens første terrorbombardement af en hovedstads civilbefolkning, var der dog sket krigsmæssige investeringer i Fladstrand. Den gamle kejserlige nordre skanse blev sat i stand, og byggeriet af den første lille kanonbådshavn blev vedtaget kort efter at krigen var gået i gang. Investeringerne skulle forhindre en engelsk erobring af Vendsyssel for at beskytte sejladsen mellem kornkammeret i Østeuropa og England.

Kanonbådene og ikke mindst kaperne, der var kongeligt autoriserede sørøvere, generede den engelske handelsflåde. Adskillige engelske handelsskibe blev opbragt, og prisedømt ved retten i enten Aalborg eller Fladstrand, som kom til at fungere som købstad under kanonbådskrigen. Det største problem for Fladstrand var, at havnen blev bygget syd for fæstningen, så englænderne kunne tilbageerobre en større samling skibe på reden. Derfor opførtes endnu en skanse, nemlig Sønder skanse, og der blev placeret et udkig på Pikkerbakken.