Kolding opstod på nordsiden af Kolding Å ved et overgangssted, hvor landevejene fra nord og øst mødtes for at krydse åen. De ældste spor af bydannelsen er potteskår dateret til 1100-tallet. De blev fundet ved Sankt Nicolai Kirke, der ligger på en skrænt omgivet af et engområde ned mod åen.
På denne tid var Kolding et trafikalt knudepunkt, og byen var med sin placering på handelsruten i Østersøområdet sikret en vigtig transithandel og dermed økonomisk vækst. Handelsvejen fra Ribe placerede Kolding i en tværgående akse, men byen lå også i en nord-syd-gående akse, da Kolding lå i grænseskellet mellem Nørre- og Sønderjylland. På åens sydside, umiddelbart øst for Sønderbro, lå havnepladsen ved Riberdyb, som det var muligt at sejle ind til, og hvorfra handelsvarerne fra Ribe fortsatte videre østpå. Første gang, byen nævnes i de skriftlige kilder, er i Kong Valdemars Jordebog fra 1231. Den ældst kendte omtale af byens købstadsrettigheder stammer fra 1321.
I 1200-tallet blev byen og dens institutioner udvidet. Koldinghus opførtes, en sognekirke af tegl, Sankt Nicolaj, en Sankt Jørgensgård samt et gråbrødrekloster omkring den nuværende Klostergade. Sankt Jørgensgården kendes fra arkæologiske udgravninger ved Sct. Jørgens Gade lige uden for den middelalderlige afgrænsning af byen. Her er fundet dele af kirkegården og dens teglstensbyggede kapel. Her er også fundet 14 ubrugte dragtspænder, som bærer indskriften »Ave Maria«, så der har muligvis været produktion af smykker i Sankt Jørgensgården.
I 1313 blev der etableret et forløb med grave og palisader omkring byen. Kong Erik Menved havde nedkæmpet et oprør uden for Kolding og lod de besejrede befæste byen. Rester af graven er bl.a. fundet mellem Skolegade og Sankt Nicolai Kirke, og hvor Helligkorsgade møder Slotsgade. Gravene fortsætter mod nord op mod Koldinghus’ slotsbankes grav.
Det middelalderlige gadenet er delvis bevaret i dag. Fra nord løber Adelgade, der er forbindelsesled mellem Låsbygade og den nordgående landevej. Byens sydlige indfaldsvej var Søndergade, der førtes over Sønderbro, og hvis brolægning der er fundet rester af. Den nu forsvundne Vestergade må have været byens hovedindfaldsvej. Udgravninger på Vestergade har vist, at gaden ændrede retning i forbindelse med anlæggelsen af Rendebanen. Fund af sporer, strigler, trensebid og en spydspids indikerer, at der formentlig blev afholdt dystrend, dvs. ringridning, på Rendebanen i middelalderen.
Der er gjort fund af huse, brønde, kulturlag, brolægninger og genstande fra høj- og senmiddelalderen en del steder inden for gravene. I Torvegade er der fundet rester af et bulhus, mens der i Adelgade, Østergade og Vestergade er fundet rester af stenfundamenter og munkestensmure. I den sydvestlige udkant af byen er der spor efter en større brand, som rasede i området på et uvist tidspunkt i 1200‑1300-tallet. I byens sydvestlige udkant fandtes en vandmølle med kanal. Møllen var delvis bygget på en kunstig ø ved åen og var i funktion frem til begyndelsen af 1300-tallet.
I 1452 fik Kolding eneret på handel i Koldinghus Len, hvilket var medvirkende til byens stærke handel i middelalderen og den efterfølgende periode. Byens borgere har blandt andet ernæret sig ved tjenesteydelser og forskelligt håndværk foruden handel. Smeden, skomageren, grydestøberen og endda en armbrøstmager på Koldinghus har da også sat deres spor i de arkæologisk fund fra byen.
I 1500-tallet bestod byen af ca. 150 gårde og huse, og indbyggertallet lå på omkring 1.500‑1.600. Skiftende kongers benyttelse af Koldinghus som residens skabte et stærkt grundlag for byens næringsliv og bragte vækst og velstand til byen. Det betød dog også øgede byrder for egnens bønder i form af ægtkørsel (dvs. pligtkørsel) for kongen.
Reformationen betød et endeligt for gråbrødreklosteret, hvis besiddelser blev overtaget af kronen omkring 1529 og sidenhen udstykket. Christian 3. stiftede byens første hospital, Sankt Jørgens Hospital, i 1558, og ved hans død i 1559 overtog enkedronning Dorothea Koldinghus som enkesæde. Hun stod bag opførelsen af latinskolen i 1566 og anlagde Slotsmøllen i 1571, hvortil der knyttede sig en afvandingskanal og en bro, som var i brug frem til 1810.
Siden begyndelsen af 1500-tallet har der ligget et rådhus på Akseltorv, og i 1582 skænkede Frederik 2. byen et nyt rådhus, hvortil der blev genanvendt tømmer fra hovedbygningen fra Viufgård. På samme tid bragte kvægeksporten til hertugdømmerne Slesvig og Holsten mange mennesker til byen, og kvæghandelen steg støt i anden halvdel af 1500-tallet.
Trediveårskrigen (1618‑48) markerede afslutningen på en lang velstandsperiode, og de mange krige og epidemier i løbet af 1600-tallet efterlod en forarmet og nedbrudt by, hvor mange gårde lå i ruiner, og befolkningen var stærkt reduceret.
I slutningen af 1700-tallet vendte udviklingen. Udførslen af stude over Kolding steg igen betydeligt, og i første halvdel 1800-tallet begyndte kornhandelen også at blive et væsentlig aktiv. Det var dog først efter anlæggelsen af en ny havn i 1843, at eksporten for alvor tog fart. Kolding fik gang i eksporten af landbrugsprodukter til Norge og København, men udviklingen af handelen var hæmmet af tilsandingen af havnen ved Riberdyb.
Omkring år 1800 var byens vigtigste næringsveje fremstilling af brændevin, jordbrug og handel. Udførslen af stude over Kolding var igen steget i slutningen af 1700-tallet, og handelen voksede i de efterfølgende år, især kornhandelen fik en øget betydning i første halvdel af 1800-tallet. Derfor blev det afgørende, at der blev anlagt en ny havn i 1843. Befolkningstallet, der i 1787 lå på 1.659, var i 1845 nået op på 2.644.
De slesvigske krige og især kampene ved Kolding d. 23. april 1849 betød en kortvarig stilstand for byen, men efter 1850 gik det igen fremad. Toldgrænsen blev i 1850 flyttet sydpå til Ejderen, konsumptionsafgiften blev ophævet i 1852, og i midten af 1800-tallet blev de første industrier, bl.a. teglværker og jernstøberier, etableret i byen.
Kolding fik sin første banegård i 1866, da den længe ventede statsbane blev ført igennem. Det fik stor betydning for den stigende handel, at jernbanenettet i og omkring Kolding voksede i de efterfølgende år, og en række privatbaner til oplandet kom til i perioden 1898‑1917. Også vejnettet blev udbygget. I hhv. 1861 og 1886 blev der anlagt et kommunalt gasværk og et vandværk, og i 1898 fulgte et kommunalt elektricitetsværk. Amtssygehuset blev bygget i 1880.
Indtil begyndelsen af 1870’erne var Låsbygade byens vigtigste handelsgade, men med banegårdens placering ved havnen og en sporføring, der gik gennem den sydlige bydel, blev handelscenteret efterhånden flyttet til Jernbanegade/Østergade-kvarteret. Handelen ændrede også karakter, idet købmandsgårde med bredt varesortiment i stigende grad blev afløst af købmænd, der specialiserede sig i engroshandel med bestemte varer eller i detailhandel. Fra 1870’erne voksede byen hastigt; befolkningstallet lå i 1901 på 12.516. Mange tilflyttere fandt beskæftigelse inden for handel og håndværk. Kolding fortsatte med at være centrum for eksport af levende kreaturer især til Tyskland. Industrialiseringen tog for alvor fart i slutningen af 1800-tallet, og nye industrier opstod, heriblandt en tobaksfabrik, et bryggeri, flere tekstilfabrikker og maskinfabrikker.
Befolkningstilvæksten resulterede i efterspørgsel efter boliger, og fra begyndelsen af 1880’erne blev der både bygget om og bygget nyt i hele den centrale del af byen. Nye kvarterer blev endvidere tilføjet på alle sider af byen. Flere store offentlige investeringer blev gennemført under og efter 1. Verdenskrig for at mindske arbejdsløsheden. Det drejede sig bl.a. om boligbyggeri i Stejlbjergkvarteret, større vejomlægninger, forlægning af åen, opførelse af vandkraftværket Harteværket, som blev indviet i 1920, og byggeriet af et nyt domhus, der stod færdigt i 1921.
Indbyggertallet, der i 1921 lå på 20.571, var herefter faldende, hvilket bl.a. skyldtes, at flere flyttede til nabosognene, hvor skattetrykket var lavere, eller emigrerede til udlandet. Hermed voksede skattebyrden for købstadens borgere, og udviklingen vendte først med indlemmelsen af områder fra Dalby Sogn (1929) og fra Vonsild, Seest og Harte-Bramdrup Sognekommuner samt Kolding Landsogn (1930), hvorved arealet fordobledes.
Med den første Lillebæltsbros opførelse i 1935 kunne Kolding fortsætte sin historiske position som trafik- og handelscentrum. Byen var på denne tid kendt for både planteskolerne og åleeksporten. Koldings åleeksport drog fordel af byens fordelagtige placering i forhold til både Østersøen, hvor ålene blev fanget, og af åen og fjorden, der gjorde det muligt at opbevare ålene i hyttefade inden videreeksport.
Efterhånden som engroshandelen vandt frem, opstod store firmaer som Sydjysk Korn og Foderstof Kompagni A/S, der efter Genforeningen i 1920 gjorde en stor del af Sønderjylland til sit opland, og som repræsenterede den voksende handel med korn og foderstoffer på havnen. Havnen spillede fortsat også en afgørende rolle som udførselshavn for kreaturer til det tyske marked.
Efter 2. Verdenskrig måtte flere gamle industrier lukke, og udviklingen gik i retning af en voksende fødevareindustri og rustfri stålindustri samt en række virksomheder, der producerede tekstildesign, bl.a. A/S Georg Jensen Damask og Beirholms Væverier. Højkonjunkturerne i 1960’erne og begyndelsen af 1970’erne betød, at der blev bygget meget nyt i Koldings gamle bymidte.
Kommunalreformen i 1970 medførte en indlemmelse af ni sognekommuner, hvor Kolding forblev administrativt center. Boligmassen blev kraftigt udvidet, og byens største sociale byggeri, Skovparken, blev opført 1971‑73. Den lokale byggematador Peter Nielsen var også med til at sikre mange privatpersoner egen bolig, og parcelhuskvarterer skød op uden for bymidten. Indbyggertallet voksede fra 41.602 i 1970 til 55.045 i 2006.
Et føtex-varehus, åbnet i 1965 i Helligkorsgade, kom til at indvarsle en ny tid for detail- og dagligvarehandelen. Kolding Storcenter åbnede i 1993, og detailhandelen blev delt mellem bymidten og en voksende detailhandelskæde i den nordlige bydel omkring Bramdrup.
Også industrien rykkede længere ud fra bymidten. Den første industri blev lagt i den sydlige del af byen, men i 1970’erne rykkede fabrikkerne nord for Kolding, hvor de skød op langs C.F. Tietgens Vej, Platinvej og Albuen.
Bysaneringen tog fart i løbet af 1970’erne og 1980’erne, hvor store dele af den gamle middelalderby blev revet ned for at skabe plads til nye og tidssvarende boliger. Vestergade og Nicolai Stræde blev ryddet for huse og erstattet af en grusbelagt parkeringsplads i en årrække, indtil Cityarkaden og Midtgården stod færdige omkring 1989. Med etableringen af motorvejsnettet omkring Kolding i første halvdel af 1970 og Billund Lufthavn mindre end 50 km derfra fastholdt Kolding sin rolle som et trafikalt og handelsmæssigt knudepunkt.
