Kilde: Familie Journal, Danmarks kirker, nr. 72

Efter mange. meget grundige ombygninger er det umuligt at se, at denne kirkes historie går tilbage til midten af 1200-tallet. Kun få partier er bevarede i deres ældste skikkelse. Den sidste, hårdhændede restaurering fandt sted 1885 og gav kirken dens nuværende udseende.

I 1575 bekostede Frederik den Anden en ombygning - det vil sige delvis, så kirken mindre en tyve år senere var "bygfældig både på tårnet og i andre måder". Samtidig havde byen pådraget sig gæld, som måtte dækkes ind andetsteds. 50 år senere modtog kirken 50 læs mursten fra Haderslev, muligvis fra det ødelagte kongeslot Hansborg.

1805 bestemtes, at kirkens nordre korsarm skulle være borgerskole. Den blev ryddet for begravelser og adskilt fra kirken samt forsynet med to etager. Men der var ikke penge til indbo, hvorfor bygningen fungerede som fattighospital og siden som infirmeri for de spanske hjælpetropper.

Lensmand på Koldinghus, Caspar Mark Danner, har blandt mange andre gravminder sin tavle i kirken. En opbyggelig tysk tekst maner mod hovmod. Formuleringen skyldes efter sigende, at nogle adelsmænd gjorde sig lystige over han herkomst. Lensmanden, sagde man, var søn af Christian III og en skomagerdatter.