Der Ort Vadsø wurde im 15. Jahrhundert von Fischern zuerst auf der Insel und ab dem 17. Jahrhundert auf dem Festland besiedelt. Die in der ersten Hälfte des 17. Jahrhunderts in der Finnmark durchgeführten Hexenprozesse führten auch in Vadsø zum Tod zahlreicher Frauen. Der Ort entwickelte sich zu einem Handels- und Verwaltungsort und erhielt im Jahre 1833 Stadtrechte.
Im 19. Jahrhundert hat es eine große Einwanderungswelle aus Finnland gegeben. Im Jahr 1875 waren 2/3 der Einwohner finnischsprachig. Auch heute wird deswegen an den Schulen noch Finnisch gelehrt.
Im Zweiten Weltkrieg wurde Vadsø von den deutschen Besatzern zur Festung ausgebaut. Diese war ein Hauptstützpunkt für den 'Unterabschnitt Nord-Varanger'. Auf der unmittelbar vor der Stadt liegenden Insel Store Vadsøya wurden Geschützstellungen und Bunker errichtet, die noch heute als Ruinen erhalten sind. Die Insel wurde in dieser Zeit erstmals über eine Holzbrücke mit dem Festland verbunden. Bei Kämpfen mit den Alliierten wurde Vadsø fast vollständig zerstört. Nur wenige Häuser blieben erhalten. Eines davon beherbergt heute das Museum.
Der urnordische Name lautete Vatnsøy, der erste Teil ist der Genitiv von vatn (Wasser) und der zweite Teil kommt von øy (Insel). Der Name bedeutet 'Insel mit Trinkwasser'.
Sehenswürdigkeiten
megalithische Steinreihe von Kiby, östlich von Vadsø
Vadsø-Museum (zeigt in der Hauptsache die Geschichte der finnischen Einwanderung)
