Festningen lot kong Håkon V Magnusson bygge her omkring år 1300. Bakgrunnen for denne manifestasjonen av statsmakt nord i riket var forholdet til datidens nabo i øst, Novgorod – riket
Anlegget, som på denne tid ble omtalt som Vardøhus slott, lå lunt til i nærheten av det som i dag heter Valen, på østsiden innerst i bukta. Slottet skal, etter gamle beskrivelser, ha bestått av bygninger, muligens utført i tømmer, omgitt av palisader, også i tømmer. Slottet omtales så jevnlig gjennom middelalderen; I 1340 beordret kong Magnus Eriksson restaurering av slottet. Det er videre avmerket på Olaus Magnus ’ kart over Norden av 1539. I 1553 overvintrer en engelsk ekspedisjon på vei til Asia der, som etter å ha oppdaget sjøveien til Arkhangelsk oppgir Asia og i stedet oppretter en handelsrute til denne russiske byen.
Kong Christian IV kommer incognito på besøk 1599. Da er slottet beskrevet med en omkringliggende mur, utført i tørrmurt skifer. Byen inntil festningen er beskrevet som dels enkle tømmerhus, dels halvt nedgravde hus, muligens gammer.
En Hollandsk tegning av byen fra 1601 (Linschouten) viser bebyggelse på begge sider av vågen, vendt mot sør. Det kongelige følge skal ikke ha vært synlig imponert over festningsanlegget, og kongen avslår å yte midler til restaurering i 1620. I 1690 er anlegget i så dårlig forfatning at residensen flyttes til nabobyen Vadsø i vest.
I 1731 sorterte Vardøhus under Bergenhus festning, og det ble dette år bestemt å iverksette arbeid med et nytt festningsanlegg for igjen å befeste rikets ytterpunkt mot øst. Vardøhus festning med sin stjerneform slik vi ser den i dag, framsto ferdig i 1739. Den ble lagt i sitt nåværende leie for å kunne beherske de tre havner i byen, noe som forteller om utstrakt virksomhet rettet mot sjøen.
Handelen mot Russland blomstrer, og Vardø får i 1789, sammen med Hammerfest, kjøpstadsrettigheter som første by etter Holmestrand i 1744 og nordligste etter Molde i 1742.
Etter å ha blitt utleid til hvalfangstvirksomhet på slutten av 1700 – tallet, gjenrustes festningen i 1807 på grunn av ufred i Europa.
Etter fredsslutningene i 1814 beskrives festningen som uten tyngre bestykning enn det som er nødvendig for å ha kontroll med den internasjonale handelsflåten som til enhver tid ligger forankret utenfor byen, og benyttes etter dette hovedsakelig til fengsel eller forlegning av soldater.