Det var den lange, tunge veien ut til Domkirken som foranlediget Strandsidens beboeres ønske om en egen kirke. På Nordnes hadde det tidligere vært flere kirker, for eksempel Mikaelskirken på Munkeliv kloster og St. Maritte kirke (Margaretakirken) nesten ute på Nordnespynten.

Erkebiskopen hadde hatt sin egen gård her fra slutten av 1200-tallet. Bygningen fungerte som handelshus fra 1300-tallet og ble drevet som en bygård. Erkestolens økonomi baserte seg på tiende, landskyld, gaver, og bøter. Kirken hadde store eiendommer i Nord-Norge, og hadde en solid økonomi knyttet til fisk. Erkebiskopens økonomi var også tidvis nært knyttet til hanseatene, som gjerne kunne stå besørge fiskeeksport ut av landet, og import av varer som erkesetet hadde behov for.

Den Nye Kirke ble reist på ruinene av erkebispegården. Som betingelse for dette ble det krevd at man vedlikeholdt den delen av kjellerne til erkebispegården som de bygget på. Restene etter erkebispegården er gravet ut i dag. Over et ca. 500 m2 stort område finner vi murrester som viser hvilket stort og flott anlegg dette må ha vært.

Ruinene av Erkebispegården er arkeologisk undersøkt, og murrester spredt over et ca. 500m2 stort område vitner om hvilket stort og flott anlegg det må ha vært. Erkebispegården ble trolig bygget i siste del av 1200-tallet, men er første gang nevnt i skriftlige kilder i 1309. Den hadde kraftige murer (ringmurer) slik at anlegget som helhet utgjorde ”en lukket karré”, og hadde nærmest et festningspreg. Murene utenfor Nykirken sto lenge. Sidefløyen i sørøst ble i 1631 omtalt som "den gamle øde Muur". Murene under kirken finnes fremdeles.

Erkebispegården ble trolig bygget i siste del av 1200-tallet, men er første gang nevnt i skriftlige kilder i 1309.

I 1637 besluttet man å bruke deler av den gamle Erkebisp-muren til begravelser, og fylte igjen fire kjellere som fortsatt sto. Etter hvert kom det til murte gravkjellere, som var oppført på privat bekostning. Da kirken brant i 1756 bygget man en ny kirke over gravkjelleren. Gravkjelleren havnet dermed under kirken men med inngang utenfra. En stund fantes det flere gravkjellere under kirken, på sjøsiden, og ned mot sjøen. Flere av gravkjellerne under kirken er nå ominnredet – til kontorer.

I 1863 gikk kirkegården helt ut av bruk. Etter brannen i 1944 ble siste del av den gamle kirkegården, som hadde strakt seg fra Strandgaten og helt ned til sjøen, sanert bort.

Nykirken brant i 1623. I de påfølgene årene ble kirken rustet opp og forskjønnet på mange vis, den fikk blant annet orgel i 1675. Nykirken brant igjen i 1756, og 23. september 1763 ble en ny Nykirke innviet. I 1800 brant også denne Nykirken, og allerede året etter hadde enda en ny Nykirke reist seg fra asken. Nå gikk det nesten 150 år uten at kirken ble utsatt for ulykker, men den 20 april 1944 kommer heller ikke Nykirken utenom eksplosjonsulykken på havnen, som forårsakte brann og alvorlige skader over store deler av Bergen sentrum, og knuste vinduer langt oppover Fjellsiden. Enda en ny Nykirke ble ikke innviet før i 1956.

Nykirkens eksteriør gir assosiasjoner tilbake til 1600- og 1700-tallet. En spennende detalj er barokkportalen fra 1670, med kong Christian Vs monogram. Ellers er kirken opp gjennom årene forsøkt holdt etter tegningene til arkitekten J. J. Reichborn fra 1700-tallet. I mange år eksisterte kirken imidlertid uten Reichborns tårnspir, noe man antar at det har vært økonomiske årsaker til. Men da kirken sto nybygd og rehabilitert i 1956, var dette med spir fra originaltegningene.

Interiørets detaljer bærer til en viss grad preg av å være fra 1950-tallet. Kirkerommet er lyst og åpent, og med prekestolen plassert som en liten altan midt på veggen.

Som en liten kuriositet kan nevnes at en Salomon Skildrer - som kan være identisk med maleren Salomon von Haven - oppførte komedier i kirken i 1636. Det dreide seg visstnok om "to hedenske historie" som vakte stor forargelse hos mange.