En el siglo XVI Vadsø era solamente una aldea de pescadores y se encontraba situada en el islote Vadsøya.