Present-day Vardøhus Fortress is the third in existence. The first was probably built in about 1302-1307 during the reign of Haakon V Magnusson. The second was built in about 1460. Both were situated on Ørtangen. The first fortress was established to maintain Norwegian supremacy over Kola and to protect the Norwegian fishing community from Karelian raids. The second, known as Vardøhus slott (castle) is known only through map references from the fourteenth century. The castle served the same function as the first fortress.

The initiative to build present-day Vardøhus came from District Governor Peter Sidelman during the 1720s. The background to this stemmed from the fact that the old fortress was, in his opinion, in very poor condition. Det kgl. Krigskommissariat (Royal War Commissariat) in Copenhagen made enquiries of Colonel Sundt, head of the Norwegian fortification service, asking for his recommendation concerning the renovation of Vardøhus, which at that time was sited on Ørtangen. Sundt advised moving the fortress. The argument was made before the king in Copenhagen concerning the significance of the defence site in withstanding Russian aggression. In 1733, the king approved designs for the new fortress. By 1739 the site was ready and was taken over by the first Commandant Ordinary, Carl von Passow.