Kolding yera una ciudá nes llendes del reinu col ducáu de Schleswig, y foi sede dun castiellu real, conocíu como Koldinghus, dende mediaos del sieglu XIII. A partir de los finales del sieglu XV Kolding sirvió daduana y de pasadoriu del comerciu colos ducaos del sur. El castiellu foi ampliáu nos sieglos XV y XVI. A mediaos desti postreru, el rei Cristián III y el so consorte Dorotea de Saxonia-Lauemburgu fixeron de la ciudá la so residencia temporal. En 1553 Cristián III fundó lhospital de San Jorge y una escuela llatina, y la reina Dorotea fundó una escuela en 1566. Nel Llibru de la Ciudá de Kolding (Koldings Bys Bog) de 1646 méntase que la ciudá cuntaba con 280 cases y 2.800 habitantes, un númberu eleváu pa una ciudá de provincia desi tiempu. Los impuestos daduana constituyeron un importante ingresu pa la corona, pero les guerres del sieglu XVII que Dinamarca llibró principalmente contra Suecia marcaron lentamu duna fase de decadencia que namái se revertiría hastal sieglu XIX. Mientres la Guerra de los Trenta Años la ciudá foi afarada en dos causes y dempués del conflictu sobrevieno la peste. Mientres una epidemia en 1654-1655 morrieron 358 persones. El 25 davientu de 1658 llibróse la batalla de Kolding, onde daneses y polacos ganaron al rei Carlos X Gustavo de Suecia, nel intre de la Guerra suecu-danesa de 1658-1660.