Da pastor Johannes Von Euch i 1864 blev sognepræst i Fredericia, var han præst for den eneste katolske menighed vest for Storebælt. Med støtte fra udlandet fik han etableret menigheder i Odense (1867), Randers (1867), Århus (1873) og Horsens (1872). Da han havde fået kontakt med nogle få katolske familier i Kolding, var det naturligt, at han også forsøgte her at oprette en katolsk menighed.

Den 29. december 1880 læste pastor Von Euch den første messe i en privat bolig og den 1. marts 1882 tog pastor Clemens Storp ophold i byen, hvor han først lejede og senere købte en tidligere beværtning “Vennelyst”, hvor præstegården og det første kapel blev indrettet. Ved hans første messe var der i alt 18 personer. Kolding blev oprettet som selvstændigt sogn den 24. september 1882.

Kun tre år efter at pastor Storp var kommet til Kolding, d.10. maj 1885, fandt grundstensnedlæggelsen til Sct. Michaels kirke sted, som blev indviet samme år d. 6. december 1885. Arkitekt Hilger Hertel fra Münster stod for byggeriet. I tårnet hænger to klokker som bærer navnet Maria (650 kilo) og Clemens (400 kilo) og blev indviet den 13. april 1893.

I 1962/63 udvidedes kirken ved to sideskibe og korvæggen fik en ny udformning. I 1968 byggedes et nyt sakristi og i 1979 blev der isat en ny mosaikrude i korvæggen, tegnet af Nis Schmidt og uført af glarmester Frese, København. Kirken har 160 siddepladser.

Sct. Michaels Skole startede 1882 i præstegården med 4 elever. I 1884 var elevtallet nået op til ti, og værelset i præstegården blev for trangt I tømrer Møllers tidligere værkstedsbygning, som i 1882 var blevet købt sammen med præstegården, blev der nu indrettet to klasseværelser. I 1886 bad pastor Storp Den guddommelige Kærligheds Søstre i Paderborn om at overtage undervisningen. 4 søstre kom og ydede i de efterfølgende 34 år en prisværdig indsats på ofte utaknemmelige vilkår. Selvom elevtallet efter 1906 voksede til 35, var økonomien skrantende. Børnene kom i vid udstrækning fra småkårshjem, hvor man ikke havde mulighed for at betale skolepenge, som kunne dække omkostningerne.

I oktober 1920 rejste kærlighedssøstrene til Silkeborg og de to første Hedvigsøstre kom til Kolding. De blev til mange flere. De byggede et hospital, en børnehave (1948) og overtog Sct. Michaels skole (1947) fra bispedømmet. Imens var Sct. Michaels skole blevet en selvejende institution og har i 2003 købt skolebygningerne fra Sct. Hedvigsøstrene. Gennem deres arbejde på hospitalet, i skolen og i børnehaven har Sct. Hedvigsøstre væsentligt bidraget til menighedens vækst og gode renommé i byen. Selvom søstrene nu har forladt Kolding, har de beriget menigheden med to blomstrende institutioner: en katolsk Sct. Hedvigsøstrenes Børnehave og en katolsk Sct. Michaels Skole – Sct. Hedvigsøstrenes Børnehave hedder i dag Sct. Michaels Børnehave efter at skolen har overtaget driften.