Oprindeligt lå der på stedet en romansk bro, der stammede fra omkring 1170, men den blev ødelagt ved en oversvømmelse i 1342. Den driftige Karl 4. var kejser på det tidspunkt, og han fik hjælp af astrologer og numerologer til at finde det præcise tidspunkt for nedlæggelsen af grundstenen til den nye bro. Dette skete 9. juli 1357 kl. 5.31 med Karls personlige deltagelse. Broen blev tegnet af den tyske arkitekt Peter Parler, og den blev opført med bøhmiske sandsten. Byggeriet blev først færdig i begyndelsen af det 15. århundrede, og da den blev taget i brug, blev der afkrævet bropenge for passage – penge, der blev anvendt til vedligeholdelse af broen.
I århundrederne siden har broen været ude for adskillige ødelæggelser og skueplads for mange historiske begivenheder. En oversvømmelse i 1432 beskadigede tre af pillerne, mens en af hvælvingerne i 1496 brød helt sammen som følge af, at en af pillerne var blevet undermineret af vand (reparationerne var afsluttet i 1503). I 1621 efter slaget ved Det Hvide Bjerg blev 27 modstandere af Habsburg-styret halshugget, og deres hoveder blev hængt op på tårnet på østsiden til skræk og advarsel for tjekkiske oprørere. Ved slutningen på trediveårskrigen i 1648, da svenske tropper besatte flodens vestbred, fandt nogle af de hårdeste kampe sted på broen, idet svenskerne søgte at indtage østbredden. Under disse kampe blev østtårnet stærkt beskadiget, og bagefter måtte alle resterne af de gotiske dekorationer fjernes.
I slutningen af det 17. og starten af det 18. århundrede fik broen det nu kendte udseende med en række barokstatuer opsat på pillerne. Under en omfattende oversvømmelse i 1784 blev fem piller stærkt beskadiget, og selv om hvælvingerne ikke brød sammen, måtte trafikken på broen i stort omfang begrænses i et stykke tid.
I starten af det 20. århundrede steg trafikken på broen betydeligt. I 1905 blev den hestetrukne sporvogn afløst af elektrisk sporvogn og tre år senere af busser. En omfattende renovering af broen blev gennemført i perioden 1965-78 i et samarbejde mellem forskellige videnskabelige og kulturelle institutioner. Pillernes stabilitet blev genoprettet, alle ødelagte sten blev udskiftet, asfaltlaget blev fjernet, og broen blev lukket for al kørende trafik.
I løbet af 1990’erne blev der rejst kritik af den seneste renovering, og en ny blev foreslået. Efter en del diskussion blev det konkluderet, at selv om den seneste renovering ikke var perfekt, var der ikke behov for et større indgreb. Efter oversvømmelserne i Centraleuropa 2002, der ganske vist ikke forårsagede større skader på Karlsbroen, blev det besluttet at reparere og stabilisere de to piller, der som de eneste ikke var blevet repareret efter 1890. Oversvømmelserne øgede opbakningen bag en generel renovering af broen, og en med start i 2005 gik renoveringen i gang med planlagt afslutning i 2007. Renoveringen har ikke krævet lukning af broen.
