Historia Najstarszy zachowany dokument odnoszący się do historii miasta pochodzi z 1321. Jest to potwierdzenie przez króla Krzysztofa II wcześniejszych przywilejów nadanych miastu przez jego poprzedników. Miasto rozwinęło się wokół kościoła powstałego w połowie XIII w. Położenie na skrzyżowaniu głównych dróg handlowych i nad fiordem sprzyjało rozwojowi handlu w okresie średniowiecza. Budowa przez przyszłego króla Danii Abla w 1248 wpłynęła na podniesienie rangi miasta, które odtąd stało się rezydencją królewską na Jutlandii i ważnym ośrodkiem politycznym. Miasto otrzymało wiele przywilejów królewskich. Szczególnie pomyślnym okresem w rozwoju gospodarczym Kolding były lata 1536–1627. Miasto było wtedy jednym z ważniejszych ośrodków handlu bydłem. Załamanie gospodarcze spowodowane zostało uczestnictwem Danii w wojnie trzydziestoletniej. Kolding był okupowany przez wojska cesarskie w 1627 doznając wielu szkód, a następnie epidemii w latach 1640 i 1654. Podczas ponownej okupacji miasta w 1644 zniszczeniu uległo wiele budynków. W czasie II wojny północnej 25 grudnia 1658 połączone siły polsko-duńskie dowodzone przez Stefana Czarnieckiego po dwudniowym oblężeniu zdobyły miasto. Kolding został jednak najpierw splądrowany przez Szwedów, a następnie przez sojuszników Danii. Podczas oblężenia uszkodzony został zamek królewski.