I Kolding Kommune er 79,1 % af befolkningen medlemmer af folkekirken, hvilket ligger over landsgennemsnittet på 74,3 % (2020). Kolding Provsti er beliggende i Haderslev Stift. Der er i alt 30 sogne fordelt på 23 pastorater. Provstiet har 42 sognepræster og 24 menighedsråd.
Efter nederlaget i 1864 blev sognene syd for Kongeå: Ødis, Vonsild, Dalby, Sønder Bjert, Sønder Stenderup, Taps, Vejstrup og Hejls tillagt Danmark i bytte for de kongerigske enklaver i Vestslesvig. Efter Genforeningen i 1920 hørte disse otte sogne under det gamle Brusk-Nr. Tyrstrup Herreders Provsti i Vejle Amt og Haderslev Stift, oprettet i 1922. Med Kommunalreformen i 1970 og Strukturreformen i 2007 kom de otte sogne under det nye Kolding Provsti, der samtidig overtog de nordlige dele af Vojens-Christiansfeld Provsti.
Med grundlæggelsen af Christiansfeld i 1773 fik den herrnhutiske brødremenighed en fast base i Tyrstrup Sogn. Missionens udsendte missionærer havde kontakt til flere sogne i Slesvig og kongeriget. Den fynske lægprædikant og bonde Peter Larsen (Skræppenborg), der var påvirket af både brødremenigheden og N.F.S. Grundtvig, flyttede i 1841 til Dons i Almind Sogn. Forinden havde han i 1835 besøgt en vakt kreds i Hjarup Sogn, hvis efterkommere i 1910 dannede Skanderup grundtvigske Valgmenighed.
Både den grundtvigianske og missionske retning havde godt tag i Kolding. I 1883 blev missionshuset Bethel bygget i byen. Kolding Højskoleforening blev etableret i 1882 af redaktøren for Højskolebladet, Konrad Jørgensen, og fik i 1889 til huse i Kolding Højskolehjem. Højskoleforeningen var aktiv frem til 2009. Ved en sognedeling i 1925 blev Kristkirkens Sogn udskilt fra Sankt Nicolai Sogn, og Kristkirken blev bygget og indviet samme år.
I Kolding Kommune findes tre grundtvig-koldske friskoler i hhv. Kolding (grundlagt 1982), Aller (grundlagt 1988) og Stepping (grundlagt 2010). Skanderup Efterskole opstod i 1914 i sammenhæng med den stedlige grundtvigianske valgmenighed. Efterskolen Kildevæld i Seest har tilknytning til Apostolsk Kirke, og Kolding Internationale Højskole (anerkendt som folkehøjskole i 1949) er en bibelskole, der også kalder sig apostolsk. Kolding Kirkecenter er en frikirke med rod i pinsebevægelsen. Den katolske Sct. Michaels Kirke i Kolding blev indviet i 1885 og har tilhørende skole.
I Kolding er der tre muslimske grupper med faste mødesteder: Bosnisk Kulturcenter Kolding, Den Somaliske Forening og Skovparkens Moske.
