Frederikshavns historie er betinget af dens beliggenhed ved kysten med direkte adgang til et af verdens vigtigste og mest trafikerede farvande. Den stigende skibstrafik måtte i 1500-1600-tallet søge læ ud for Fladstrand inden turen nord om Skagens Odde. I 1568 var der 16 huse i byen, og formentlig var en del af disse beboet af skipperkøbmænd, som drev handel langs Kattegats kyster.
Den første skanse ved det lille fiskerleje Fladstrand blev bygget af de kejserlige tropper 1627-29 for at beskytte havnen, og op mod år 1700 blev befæstningen udvidet med yderligere et citadel med et martellotårn og en skanse på den lille ø Deget. Efter 1669 overtog Fladstrand tolddeklareringen fra Sæby, og under Store Nordiske Krig spillede byen i 1710’erne en vigtig rolle som base for krigsskibe, der bl.a. konvojerede handelsskibe mellem Danmark og Norge. I disse år kom byen op på ca. 580 civile beboere og omkring 200 militærfolk. Efter krigen faldt befolkningstallet igen, og i 1801 havde Fladstrand kun 463 indbyggere.
Indtil 1805 benyttedes det ret dybe vand i læ af Hirsholmene og Deget til opankring, men i slutningen af 1700-tallet begyndte kampen for en egentlig havn. Med den nye toldlov, Toldforordningen af 1797, blev udenrigshandelen liberaliseret, hvilket gav en øget skibstrafik og medførte, at Fladstrand i 1806 fik sin første havn. Englandskrigen (1807-14) betød dog, at byggeriet først blev genoptaget i 1830’erne. Under Englandskrigen havde Fladstrand fået flere købstadsinstitutioner, og med købstadsrettighederne i 1818 steg befolkningstilvæksten. I perioden 1818-34 fordobledes befolkningstallet i byen, der nu bar kongenavnet Frederikshavn. I slutningen af 1840’erne begyndte dampskibene at sejle i fast rutefart mellem Frederikshavn, København, Christiania (Oslo), Christianssand (Kristiansand), Newcastle og Göteborg.
Efter adskillelsen fra Norge i 1814 mistede fæstningen sin militære betydning. Garnisonen blev nedlagt i 1864, og arealerne frigivet i 1880’erne, hvorefter udviklingen af havn og værft opslugte fæstningsområdet.
Da den østjyske længdebane i 1871 nåede til Frederikshavn, oplevede byen endnu et opsving; fra 1870 til 1916 blev antallet af indbyggere firedoblet (fra 2.133 til 8.532), og byen fik egne pengeinstitutter, træskibsværfter og motorfabrikker. Havneudvidelsen 1883-93 betød, at havnen blev landets næststørste provinshavn, hvilket sammen med industrialiseringen af fiskeriet gjorde, at Frederikshavn frem til 1930’erne var landets største fiskerihavn. Samarbejdet mellem de frederikshavnske vodbindere, værfter, motorfabrikker, kutterrederier og fiskeeksportører gjorde Frederikshavn til et mønster for dansk fiskeri. Et af skibsværfterne begyndte kort efter år 1900 at bygge skibe i stål.
Industrialiseringen fik indflydelse på byens politiske udvikling. De mange industriarbejdspladser og arbejdspladser på havnen betød stor tilvandring af arbejdskraft, og Socialdemokratiet fik i 1930’erne stadig mere magt i byrådet. Flere store fiskekonservesfabrikker blev anlagt, og her blev der især anvendt kvindelig arbejdskraft. Samtidig skød mange minkfarme op, som aftog fiskeaffaldet fra virksomhederne på havnen.
Et hovedmål for den tyske besættelse af Danmark i april 1940 var Frederikshavn Havn, der var nødvendig for de tyske troppetransporter til Norge. Frederikshavn blev gjort til et af fire forsvarsområder i Danmark, og besættelsesmagten opførte ca. 350 bunkeranlæg i området. Da besættelsesmagten havde trukket sig tilbage, blev det tyske forsvarsanlæg for havnen ombygget til det danske forsvar.
Efter 2. Verdenskrig kom der atter gang i den nordiske sejlads, og fra 1960’erne kunne svenskere tage på fornøjelses- og indkøbstur til Frederikshavn. Sejladserne udviklede sig til, at Frederikshavn blev Europas mest trafikerede færgehavn. Samtidig med byggeriet af flådehavnen i 1950’erne blev der også bygget en stor fiskerihavn til de mange nye stålkuttere, som havde hjemhavn i byen. I 1962 blev Flådestation Frederikshavn anlagt i en del af havnen. Byens befolkningstal nåede i 1970 op på 24.846.
Kommunalreformen i 1970 gav Frederikshavn begrænset vækst. Oliekriserne og stigende oliepriser i 1970’erne medførte, at byens fiskerflåde flagede ud og flyttede til vestkysten for at komme nærmere fiskepladserne i Nordsøen. EF’s og senere EU’s fiskeripolitik og ændringer i dagpengereglerne betød, at byen mistede mange af de arbejdspladser, der typisk havde været besat af kvinder. I 1999 lukkede byens største arbejdsplads, stålskibsværftet Danyard A/S. Ørskov Stålskibsværft A/S måtte kort efter give op, men blev i 2003 rekonstrueret som reparationsværft under navnet Orskov Yard A/S. Motorfabrikken B&W Alpha Diesel blev i 1983 overtaget af tyske MAN. Omkring år 2000 indskrænkedes det toldfrie salg på færgerne til Sverige, og byen fik vanskeligere ved at tiltrække svenske turister, der ellers var en stor del af kundegrundlaget for byens forretningsliv. Ikke desto mindre blev der taget beslutninger i kommunalbestyrelsen og i erhvervslivet, som betød, at byen ikke gik i stå. Ved statens salg af statshavne opkøbte Frederikshavn Kommune havnen med virkning fra 2001. Havnen skulle fortsat være erhvervshavn, og erhvervslivet begyndte at investere i byen.
