Nykirkegården, ved Nykirken stammer fra 1637, da fire kjellerrom under ruinene av Erkebispegården ble gjenfylt og brukt som gravplass. En privat gravkjeller fra 1681 kom til å ligge under kirkegulvet da kirken ble gjenreist etter brannen 1756. Kirkegårdsmurene ble revet 1767, men gjenreist, og endelig fjernet først 1872. Nykirkegården ble nedlagt som gravplass 1863, og sørøstre del av den ble overtatt av havnevesenet 1883. Resten har etter den annen verdenskrig fått parkmessig behandling. Det er tatt vare på en rekke gravminner, bl.a. for Hans Jacob Grøgaard, eidsvollsmann og sogneprest til Nykirken, og biskop Jacob Neumann. Kirkegården har minneplater for bakermester Johan Jacob Dekke og hustru Anna Engel Dekke, kjøpmann Amund Helland og hustru Malene Helland, eidsvollsmannen og sogneprest til Nykirken Jonas Rein (oppsatt 1914), arkitekt Johan J. Reichborn (oppsatt 1938) og rester av en minneplate for Anne Richardsdotter (Pett Anne, se Petanebryggen). Gravkjellerens levninger av Lundefamiliens gravlagte ble 1862 flyttet til Mannsverk (Nils Lundes Minde).