Vadsø kirke er en langkirke fra 1958 i Vadsø. Den ble oppført i perioden 1954–1958 og innviet 30. mars 1958. Arkitekt for kirken var Magnus Poulsson. Dette er Vadsøs fjerde kirke, og den ble bygd i prosessen der man gjennoppbygde Vadsø etter krigen. Byens forrige kirke ble ødelagt av krigshandlinger 28.-29. oktober 1944.
Kirken er i betong og har 415 plasser. Den er oppført på samme sted som byens forrige kirke, men er orientert nord-sør. Denne orienteringen henger sammen med den øvrige byplanleggingen som ble gjort da man måtte gjenoppbygge Vadsø etter andre verdenskrig. Utvendig er kirken dekorert med relieff i fasadebetongen. Vendt mot byen har den en høy og mektig front med to tårn og en gavl over. På sidene av tårnene er det store ur. Under gavlen, mellom tårnene, er det et gyllent spir som står over hovedinngang til kirken. Mellom spiret og inngangsdøren står en skulptur av apostelen Peter, laget av Tone Thiis Schjetne.