Eldste omtale av en kirke på (gnr. 9) Vadsø er i 1589 (Wadtzøe, Thr.R. 92). Wadzöen omtales på slutten av 1500-tallet som et stort fiskevær (Storm 1895). Den første kirken sto på Kirkeøya (= Store Vadsø, NG 276) under (gnr. 9) Ved Vadsø omtrent midt på nordsida ca. 100 m øst for den nåværende brua over til fastlandet, jf. ID 28318 Gamle Vadsøy kirkested. Den ble revet rundt 1710, og noe av materialene ble gjenanvendt i kapellet på Angsnes bygd 1719. Nykirken, en tømmerbygning med korsformet grunnplan og tårn (Sollied 1901:306), ble reist i 1709 og innviet 1711 på Skattøra inne på fastlandet, 800-900 m rett nord for det middelalderske kirkestedet i vestre del av nåværende kirkegård. Denne kirken gikk ut av bruk i 1861 og ble revet i 1869. Våpenhuset ble stående og ble benyttet til ”gravkapell”. Ny kirke ble reist på Galgebakken i 1858-61 og innviet sistnevnte år. Denne ble brent i 1944, og først i 1958 ble nåværende kirke bygd – også den på Galgebakken.