It is located in the town of Vardø on the island of Vardøya on the Barents Sea near the mouth of the Varangerfjord in northeastern Norway near the Russian border.

In 1251, an embassy from the Republic of Novgorod to King Haakon IV Haakonson of Norway complained of clashes between the Norwegians and the Karelians in northern Finnmark.

Finnmark remained important as a fishery; the fish was shipped as stockfish to Bergen and traded there with the Hansa merchants.

While visiting the fort in 1511, Erik Valkendorf wrote: "the country would not be habitable for Christians were it not that the catch of fish is so plentiful as to attract people to settle down there.

[8] In 1597, Boris Godunov, the regent of Russia, wrote to King Christian IV of Denmark and Norway, asserting that Vardøhus and "the Lapp country (as far as Tromsø) was from ancient times a perpetual patrimony of the Czar."

As a result of these border conflicts with Russia, King Christian IV of Denmark and Norway asserted Norway's historic ownership and visited Vardøhus in 1599 to instruct the governor of Vardøhus to collect taxes from Russians in his province, including the Kola peninsula and to exclude the Swedes, who were also attempting to claim the territory based on the Treaty of Tyavzino.

[12] During the period from the beginning of the Second World War to the German invasion of Norway, Vardøhus Fortress was an active unit under the command of Naval District no.

[13] For a time during the Winter War, 15-20 Finnish soldiers were interned at the fortress after being pushed across the border from Northern Finland by Soviet offensives.

[12] The weapons at the disposal of the garrison in 1940 were:[12] During the evening of 9 April 1940 Captain Basilier received orders to mobilize a small number of additional soldiers to guard the fortress.

[12] Captain Basilier, who had been suffering from poor health since Easter that year, took sick leave on 13 April and was replaced by Navy Lieutenant B. Bjerkelund.

From this date a full mobilization was carried out in the Vardø area, in addition the members of the local rifle association were deployed to guard duty at important objectives.

[12] On 20 April 1940 the commander in chief of Northern Norway, General Carl Gustav Fleischer, issued orders to the 3rd Naval District that an internment camp for German prisoners of war was to be established at Vardøhus.

Most of the German prisoners were crew members from the Kriegsmarine destroyer Erich Koellner, sunk at Djupvik on the southern side of the Ofotfjord during the Battles of Narvik.

Nova was escorted southwards by the patrol boat Ingrid – a captured German trawler operated by the Royal Norwegian Navy.

Since early May German aircraft had overflown the area without incident, but on 4 June a single Luftwaffe bomber made an attack.

After expending its bomb load, the bomber flew low and strafed the area, riddling the radio hut and other buildings with bullets.

[12] On 8 June Lieutenant Bjerkelund was informed that the fighting in Norway was coming to a close and given the opportunity to evacuate to the United Kingdom.

[22] In 1944, as the Germans retreated from Finland through Finnmark before the advancing Finns, General Lothar Rendulic ordered a scorched earth policy.