I fästningstornets nedre våning inreds 1658 en kyrka, men som invigs först 1708. I samband med att Gamla Älvsborgs rivs 1671, läggs dess kyrka ner och ett antal medaljongporträtt i olja flyttas över till Nya Älvsborg, där de idag utsmyckar räcket till läktaren. De föreställer Frälsaren, Moses, Jesaja, Jeremia, Hezekiel, Daniel och evangelisterna – Kristus på korset finns på altartavlan. Ovanför altartavlan hänger en kopia av ett porträtt av Karl XII, en i kyrkliga sammanhang troligen unik placering. Originalet, i guldram anses tillhöra ett av de bästa porträtten av Karl XII och finns sedan 1917 på Göteborgs Museum.

Den 18 april 1869 hölls den sista kyrkostämman här med Nya Elfsborgs församling. Den 14 juni 1871 fastställer Kungl. Maj:t att Nya Älvsborg i kyrkligt avseende ska tillhöra Lundby församling, och att dess kyrkokassa och inventarier ska överlämnas till denna församling. I Lundby gamla kyrka hänger från den tiden ljuskronan från Nya Älvsborg. 

Kyrkan på Nya Älvsborg är en av de bäst bevarade från Karl XIIs tid. Under Tordenskjölds andra slag mot Göteborg, 1719 mitt under pågående gudstjänst far en tolvpundig massiv kanonkula in genom ett fönster i kyrkan, slår av benet på en soldat och ränner rakt in i den motsatta väggen. Där sitter den kvar ännu.