Vadsø ble bombet av det sovjetiske flyvåpen utover sommeren og høsten 1944, som del av den sovjetiske offensiven mot den tyske okkupasjonsmakten i Norge. Sammen med Kirkenes og Vardø var byen blant de få som ble bombet av Sovjetunionen i Nord-Norge. Ødeleggelsene arter seg derfor noe annerledes enn i de byene som ble ødelagt av den tyske okkupasjonsmakten som del av den brente jords taktikk. I hovedsak ble bysentrum bombet, og presisjonen var mindre enn i dagens offensive luftkrigføring. Det finnes derfor bevarte anlegg fra tiden før krigen i utkanten av Vadsø.
Etter krigen ble Vadsø gjenstand for planlegging og gjenreisning gjennom det statlige programmet ”Brente steders regulering” (BSR). Arkitekt Johs. L. Borchenius hadde ansvaret for reguleringsplanen som ble vedtatt i 1946. Den største delen av sentrum slik det fremstår i dag, er bygget opp etter BSRs planer. Det ble tatt utgangspunkt i sentrum av byen slik det var før krigsødeleggelsene, og man skapte et bybilde med de viktigste og mest sentrale funksjonene som torg, hotell og rådhus i byens midte.
I Vadsø er rådhuset, planlagt gjennom BSR, det mest prominente bygget. Den høye bygningen er monumentet som, ved siden av den listeførte kirken beliggende noe høyere over byen (Amtmannsgata 1), dominerer Vadsøs silhuett.
Vadsø kirke, en langkirke betong fra 1958, ble oppført i perioden 1954 til 1958. Arkitekt var Magnus Poulsson. Kirken er oppført på samme sted som den gamle korskirken fra 1861, som ble lagt i ruiner under bombingen høsten 1944. Dagens kirke ligger som et monumentalt bygg, med en ruvende front som peker sørover i Kirkegata. I kirkesammenheng er det uvanlig at kirkeskipet er plassert fra sør til nord på dette viset, da det vanlige er øst-vest. Denne plasseringen inngikk i planen fra 1946, og kan sies å fremheve kirkens monumentale funksjon øverst i Kirkegata.
Videre er sentrumskvartalene omkranset av gateløpene Ørtangen – Brugata – Oscars gate med sjøen som sør-østre avgrensning, fremdeles bevart strukturelt og for størstedelen også bygningsmessig som et resultat av gjenreisningsbyggingen. Områdene som omkranser sentrumskvartalene spiller videre på strukturen disse danner, og kompletteres av et helhetlig skoleanlegg i tilknytning til Amtmannsgata, også oppført etter krigen.