Other notable villages included Ekkerøy, Kiby, Krampenes, Skallelv, Valen, and Vestre Jakobselv.

[7][8] The kjøpstad (market town) of Vadsø was established as a municipality on 1 January 1838 (see formannskapsdistrikt law).

The municipality (originally the parish) is named after the Varangerfjorden (Old Norse: Verangr or Verjangr).

The first element is verja which is the plural genitive case of the word which means "fishing village".

On 3 November 1917, a royal resolution changed the spelling of the name of the municipality to Nord-Varanger.

[11] The municipality was located on the southern half of the Varanger Peninsula, east of the Jakobselva river, along the Varangerfjorden.