Haderslev opstod på en højtliggende sandbanke i bunden af Haderslev Fjord, og byen lå i middelalderen afgrænset af vand eller fugtige områder på alle sider. Arkæologiske udgravninger i Dannevirkestræde ved Møllestrøm har vist, at der i 1100-tallet opstod en bebyggelse på bankens vestside ned mod Jernhyt Bæks udløb i fjorden.
Byen omtales første gang omkring år 1200, da Saxo i Gesta Danorum beretter, »at Harald Hildetand dræbte Kong Hader i Jylland, der hvor der endnu ligger en by, der bærer hans navn«. Byen fik en kvaderstenskirke omkring 1175, og havnen blev en vigtig stabelplads i forbindelse med udvekslingen af varer mellem Østersøen og Ribe ved Vesterhavet.
I løbet af 1300- og 1400-tallet udviklede Haderslev sig til at blive en af de større byer i hertugdømmet, idet den nød godt af sin placering som den eneste købstad i den nordlige del af Sønderjylland. Byen blev i løbet af 1400-tallet det nordligste toldsted for okser i hertugdømmet, hvor alle okser fra Kolding og Assens skulle erlægge told, inden de blev drevet videre mod syd med henblik på slagtning. Under kong Erik af Pommern blev der etableret en stor mølle ved byen, og Haderslev Dam blev da skabt som mølledam. Vandstanden blev hævet op til 2 m vest for byen, hvilket muliggjorde, at vandet via en kanal kunne føres nord om byen langs Gravene og Jomfrustien og ud i fjorden. Kanalen har givet navn til Gravene. På samme tid blev kirken ombygget, bl.a. med et nybygget gotisk kor, og i løbet af århundredet skete en gradvis udvidelse af kollegiatkapitlet til en stor gejstlig institution med op til 20 tilknyttede kannikker. Den slesvigske biskop lod opføre en bispegård i byen.
Det middelalderlige gadenet er i store træk bevaret. Hovedstrøget fra havnen over byens centrale torv mod Ribe gik langs Badstuegade, hvor havnekajen lå, og videre ad Højgade, hvor rådhuset lå, og ad Torvet, Apotekergade, Bispegade og Storegade. Præstegade førte mod dominikanerklosteret, mens Slotsgade og gadeforløbet Lille og Store Klingbjerg førte til borgen. Nørregade blev fra 1400-tallets begyndelse i stigende grad benyttet af de talrige oksetransporter ud mod Immervad Bro. Byens tre byporte synes opført i 1420’erne efter etableringen af kanalen nord om byen. Der er fundet fundamenter af Bispeporten i Bispegade samt af Nørreport i Nørregade, begge inden for voldgraven. Der er flere steder i byen udgravet rester af byens senmiddelalderlige stenhuse, fx Højgade 1, samt Marianerpræsternes Hus for enden af Præstegade. I Apotekergade 11 er kælderen under præsteskolen fra 1465 udgravet og restaureret, og endelig er kælderen under Slotsgade 22, der har tilknytning til Haderslevhus, også bevaret.
I 1525 tildelte Frederik 1. sin ældste søn, Christian (den senere Christian 3.), Haderslev og Tørning Len som underhold, og Haderslevhus blev centrum for et hertugeligt hof samt for Christians gennemførelse af Reformationen i Hertugdømmerne.
Haderslevs storhedstid lå fra midten af 1500-tallet til midten af 1600-tallet. Det havde stor betydning for håndværkere og købmænd, at Haderslev var den foretrukne residensby i hertugdømmet Slesvig, når kongen kom til landsdelen. Hansborg Slot stod færdigt i 1585. De fysiske rammer for byen sprængtes, og med en blomstrende skibsfart var Haderslev stadig handelsby for et stort opland.
En af Danmarks ældste latinskoler, Haderslev Katedralskole, blev oprettet i 1567.
Haderslev led hårdt under Trediveårskrigen, da størstedelen af byen blev sat i brand i 1627. Der gik mere end 50 år, før byen var ved at være genopbygget. I 1700-tallet fulgte en økonomisk nedgang; i 1759 blev Haderslev igen hærget af en brand, hvorunder 170 af byens 343 huse nedbrændte, og grundlæggelsen af Christiansfeld i 1773 betød, at håndværkerne i Haderslev fik hård konkurrence om afsætning af varer på landet.
I 1753 blev byen fast garnisonsby, da Holstenske Rytterregiment, fra 1816 med navnet Holstenske Lansenerregiment, blev forflyttet hertil. Regimentet blev opløst i 1842, men med preussiske enheder i 1864 blev Haderslev igen garnisonsby.
Med opmudringen af havn og fjord i årene 1829‑32 samt anlæggelsen af en skibsbro kom der gang i skibsfarten, og en fornyet uddybning 1857‑62 gjorde det muligt at bygge store sejlskibe.
Fra 1830’erne og frem til 1864 blev der grundlagt en lang række industrivirksomheder. Befolkningstallet steg kraftigt: i 1801 lå det på 2.685, men var i 1845 steget til 6.128. Krigen i 1864 og indlemmelsen i 1867 af hertugdømmerne Slesvig-Holsten under Preussen fik de nationale modsætninger til at vokse. Samlingspunktet for de dansksindede i Haderslev blev Selskabet Harmonien (stiftet 1849).
Haderslev oplevede stagnation, konkurser og stor udvandring i årene efter 1867. I 1870 lå indbyggertallet på 8.258. Udviklingen ændredes fra midten af 1880’erne, hvor bl.a. Haderslev Statsseminarium blev oprettet i 1884, og de følgende år frem til 1914 kom en række nye skoler til, bl.a. en husholdningsskole og en landbrugsskole.
Med opførelsen af Haderslev Kaserne i 1888 og med Haderslevbanen til Vojens fra 1866 og anlæggelsen af Haderslev Amts Jernbaner i årene 1899‑1910 blev Haderslev et knudepunkt for handelen med landbrugsvarer. Der anlagdes flere virksomheder som Schaumanns Klædefabrik i 1872 og Bryggeriet S.C. Fuglsang i 1865. Forstæderne Sønder Otting, Haderslev Ladegård og Gammel Haderslev blev i 1910 lagt sammen med byen Haderslev.
Haderslev byråd bestod i perioden 1867‑1918 kun af medlemmer fra den tyske liste, men dette ændrede sig i 1919, da alle over 20 år fik stemmeret, og ved byrådsvalget i marts samme år fik den danske liste absolut flertal.
Ved folkeafstemningen i 1920 om Nordslesvigs nationale tilhørsforhold stemte Haderslev som eneste købstad for tilhørsforhold til Danmark. Haderslev var ved Genforeningen en slidt by, og boligmanglen var stor. Fra 1921 til 1940 blev der opført 724 ejendomme; især i årene 1930‑35 var byggeaktiviteten stor med offentlige støtteordninger og billige lån. Fra 1950’erne blev særligt villaer og parcelhuse bygget på kolonihavegrunde, som var blevet udlagt i 1920’erne og 1930’erne. Indbyggertallet voksede fra 13.149 i 1921 til 18.276 i 1950. Til de to større skoler, Hertug Hans Skole og Louiseskolen, blev der i 1924 tilføjet endnu en skole, Sct. Severin Skole.
Haderslev Amts Jernbaner blev lukket i årene 1932‑39, og persontransport fra oplandet til byen blev nu overtaget af busser. Trafikken igennem byen blev et større og større problem i de smalle gader. I 1946 vedtog byrådet at anlægge en omkørselsvej. Vej og dæmning blev anlagt 1948‑58, og samtidig blev Haderslev Dampark anlagt i 1958.
Under Besættelsen kom det d. 8. december 1940 til hårde kampe mellem politi og medlemmer af det danske nazistparti DNSAP, der uniformeret og med spader ville marchere igennem byen og efterfølgende afholde møde. Spadeslaget, som begivenheden blev kaldt, førte til arrestationen af 350 deltagere.
Ved Kommunalreformen i 1970 blev Haderslev Købstadskommune sammenlagt med ti sognekommuner til Haderslev Kommune, hvor Haderslev blev det administrative centrum. Samtidig mistede byen sin funktion som sæde for Haderslev Amt, der havde eksisteret siden 1920. Et nyt rådhus til afløsning af det gamle rådhus i Lavgade blev opført i 1974. Haderslevbanen lukkede for persontrafik i 1978. Indbyggertallet lå i 1970 på 20.042 og holdt sig nogenlunde stabilt; i 2006 lå det på 21.140.
