Nyborg opstod tidligt i 1200-tallet som borgby til Nyborg Slot, og både borgens og byens oprindelse og udvikling er tæt forbundet med beliggenheden ved Storebælt. Nyborg Fjord var den eneste oplagte naturhavn mellem Kerteminde i nord og Svendborg Sund i syd. Ved udmundingen af Nyborg Fjord ligger Slipshavn, der fungerede som Nyborgs fremskudte havn. Fra Slipshavn kunne bæltet overskues, men placeringen var meget udsat. Derfor måtte borgen og byen placeres i mere beskyttede omgivelser inderst i fjorden. Nyborg var også det naturlige overfartssted til Tårnborg og senere Korsør.
Byen blev anlagt på morænebakkerne inderst i fjorden, og det middelalderlige gadenet er i hovedtræk bevaret i form af de øst-vest-gående hovedgader Nørregade, Mellemgade og Kongegade og de to tværgader Korsgade og Adelgade. Syd for byen strakte strandarealer sig i middelalderen mod øst og vest. Vanddybden syd herfor var ikke egnet for større skibe, der måtte ankre op ved Holmen (Nærmerøen) og Slipshavn (Knudshoved) øst for byen, hvor der var dybt vand tæt ind til land.
Nyborg fik formentlig købstadsprivilegier under kong Valdemar Sejr. Nyborg Slot fungerede som det lovfæstede mødested for det middelalderlige parlament, danehoffet, og Nyborg fik derfor en helt særlig status som kongeby og danehofby.
I årtierne efter Reformationen udbyggede Christian 3. Nyborg til en prægtig residensstad. Som led i dette blev Kongens Skibsbro anlagt, hvorefter det blev muligt for større skibe at sejle direkte ind til byen. Med Frederik 2. skiftede kongemagten dog fokus til Nordsjælland, siden København. Frem til midten af 1600-tallet var byen relativt velhavende.
Under Karl Gustav-krigene 1657‑60 blev Fyn i januar 1658 besat af svenskerne, og også Nyborg blev indtaget. Svenskernes brutale hærgen gik hårdt ud over både slottet, byen og dens indbyggere. Et af de helt afgørende vendepunkter var dog Slaget ved Nyborg d. 14. november 1659. Som plaster på såret for krigens trængsler fik Nyborg i 1661 privilegier som stabelstad med ret til at drive udenrigshandel til og fra Fyn.
Efter svenskekrigene stod det klart, at fæstningen måtte forstærkes. Nyborg havde status som fæstningsby og var i vid udstrækning præget af militærets tilstedeværelse. Nyborgs historie og erhverv var også tæt forbundet med det maritime. I 1700-tallet var Nyborg omdrejningspunkt for en omfattende skibstrafik. For at kontrollere passagen gennem Storebælt var der udstationeret vagtskibe, som forblev ved Nyborg frem til Strøm og Sundtoldens ophævelse i 1857. Samtidig havde Nyborg en vigtig funktion som overfartssted. I 1828 blev det første dampskib, Mercurius, indsat på ruten Nyborg-Korsør. For trafikken til lands fik det stor betydning, da hovedlandevejsnettet blev udbygget i 1840’erne. Hvor indbyggertallet i 1787 lå på 1.672, var det i 1855 steget til 3.565 indbyggere.
Indtil 1869 var Nyborg en fæstningsby, og i 1913 blev også garnisonen nedlagt. Hermed var byens lange militære historie endegyldigt slut. I 1865 blev hovedbanen på tværs af Fyn indviet, hvilket fik stor betydning for Nyborg. I 1883 blev de første jernbanefærger sat ind på Storebæltsoverfarten, og i 1897 blev jernbanenettet udbygget med forbindelsen til Ringe og Svendborg.
Nyborg fik flere store institutioner, fx Døveskolen i 1891 og Nyborg Statsfængsel i 1913. Nyborg Havn blev udbygget flere gange og spillede en stadig større rolle som både trafikhavn og industrihavn. Det betød, at Nyborg først og fremmest var en tjenestemandsby med mange ansatte ved færgerne, jernbanen og de statslige institutioner. Dog var der også jernstøberi og tobaksfabrik i byen. Med grundlæggelsen af Nyborg Badehotel (i dag: Nyborg Strand) i 1899 indledtes en ny æra for Nyborg som hotel- og konferencested.
Nyborgs funktion som trafikknudepunkt blev styrket og er en vigtig årsag til byens vækst i 1900-tallet. Mens der i 1921 var 10.223 indbyggere i byen, var tallet i 1970 steget til 14.270. Havnen blev udvidet flere gange, og trafikken over Storebælt oplevede en kraftig vækst. Udbygningerne af både færgelejerne og jernbanen samt ikke mindst det store gadegennembrud i 1935 satte sig spor i byen. Efter 2. Verdenskrig skete der en voldsom vækst i trafikmængden, og i 1955 skulle der hele syv jernbanefærger og tre bilfærger til for at klare presset. I 1957 blev bilfærgerne flyttet uden for Nyborg til Knudshoved med overfart til Halsskov på Sjælland.
Der var en større skibstrafik til og fra Nyborg, og flere større industrivirksomheder blev anlagt ved havnen, fx Dansk Esso A/S, som ved anlæggelsen i 1919 var Nordens største olie- og benzinlager. En anden var De Danske Gasværkers Tjærekompagni A/S, ligeledes grundlagt i 1919. I 1941 byggede Tjærekompagniet en kemisk fabrik.
Med den faste forbindelse over Storebælt, der åbnede i 1997 (jernbane) og 1998 (biltrafik), ændredes Nyborg fra færgeby til broby. I 1994 overtog Nyborg Havn Lindholm Havn fra Storebæltsforbindelsen A/S, og i de følgende år blev der arbejdet på at udvikle havnen til en såkaldt feederhavn; dette skulle fremme dens muligheder for at modtage og afskibe tungt gods. I løbet af de følgende år blev der investeret massivt i Lindholm Havn, der sammen med Avernakke Terminalen udgør industrihavnen. Nyborg formåede fortsat at tiltrække både store institutioner og virksomheder, fx den store institution Strandvænget for fysisk og psykisk handicappede. Kommunekemi blev grundlagt i 1971 og var det første tværkommunale anlæg i Danmark til håndtering af farligt affald. Indbyggertallet lå i 2006 på 16.043.
