Folkekirkens medlemsandel i Nyborg Kommune udgør 81,5 %, hvilket ligger over landsgennemsnittet på 74,3 % (1. jan. 2020). Kommunen rummer i alt 19 sogne: Nyborg Provstis 15 sogne samt fire sogne i Kerteminde Provsti. Der er 13 landsogne med under 1.000 indbyggere, og syv ud af ti pastorater i kommunen er to- eller tresognspastorater. Nyborg Sogn er det eneste sogn med en medlemsprocent under 80 %. Det er samtidig det medlemsrigeste sogn i kommunen og var et ud af to sogne på Fyn, hvor der fortsat var afstemningsvalg til menighedsrådet i 2016. Her samarbejder medlemmer fra hhv. en grundtvigiansk, indremissionsk og socialdemokratisk liste. Menighedshjemmet på Nørrevoldgade, opført 1890‑91 af Nyborgs menighedsråd, har både været brugt til bespisning af fattige børn, til søndagsskole, fælles koraftener m.m. og som missionshus for Indre Mission i Nyborg. Grundtvigianere i Nyborg stiftede i 1913 Højskoleforeningen for Nyborg og Omegn, hvis bygning blev solgt til Frimurerlogen i 1969.
Conrad Frederik Kisbye var præst i Aunslev og Bovense Sogne fra 1844- 1889 og medskaber af en af de første grundtvigianske vækkelser i kommunens område. Refsvindinge Friskole er stiftet i 1865 i Vindinge af en kreds omkring en tidligere lærer fra Danmarks første friskole i Dalby med støtte fra bl.a. sognets grundtvigianske præst. Skolen har siden 1903 ligget i Refsvindinge og følger de grundtvig-koldske skoletanker.
En ledende kreds fra Indre Mission i Danmark købte i 1912 Nyborg Badehotel, hvor de indrettede et missionskursted til bl.a. de kendte Nyborgmøder, som endnu afholdes en gang årligt. Hotellet har siden årtusindskiftet været ejet delvis af en fond knyttet til Indre Mission og har siden Storebæltsforbindelsens indvielse 1997-98 haft kommerciel succes som konferencehotel.
Nyborg Adventistkirke har været i Nyborg siden 1922, fra 1974 i kirken i Nybrogade, bygget af menighedens forstander, som var murer. Nyborg katolske menighed, stiftet i 1907, blev nedlagt i 2016 pga. nedgang i medlemstallet. Menighedens skole lukkede i 1996 og omdannedes til Nyborg Friskole, som i 2016 også overtog Stella Maris Kirke (opført 1928).
Nyborg Somalisk Forening, stiftet i 1990’erne, har bederum og foreningslokaler i en kælder i Adelgade. Den tyrkiske Nyborg Moské (Nyborg Tyrkisk Kulturforening) på Landrovej er stiftet i 2002. I 2004 blev der indrettet et bederum og ansat en imam i Nyborg Fængsel; dette blev dog i 2006 afløst af flere mindre bederum fordelt på afsnittene.
