Stubbekøbing, der opstod ved et åudløb, omtales første gang i 1282, og de ældst kendte købstadsprivilegier er fra 1354, men kirken er fra 1100-tallet. Sandsynligvis opstod den ældste bebyggelse på samme tid. Her lå et nor, som dannede en naturhavn, men efter at der blev anlagt en dæmning ved noret, måtte skibene lægge til ankers ved kysten. Sildefiskeriet i Øresund havde afgørende betydning for Stubbekøbing i senmiddelalderen, og omkring år 1500 havde byen et leje med plads til 66 boder på Falsterbo.
Da sildestimerne ophørte efter ca. 1550, kom Stubbekøbing ind i en krise, der varede til ca. 1830 og bl.a. blev forstærket af flere store brande i 1500- og 1600-tallet, en stormflod i 1625, hvor ca. 40 fartøjer gik tabt, og især krigen mellem Danmark og Sverige 1658-60, under hvilken 34 gårde blev nedbrudt. Det er blevet beregnet, at byen havde ca. 3.500 beboere omkring år 1500, men i 1672 var der kun 511, og i 1787 var det faldet yderligere til 467. I 1700-tallet havde Stubbekøbing to specialer, kridtpibefabrikation og pottemageri, hvis produkter blev afsat i store dele af Danmark.
Befolkningstallet voksede imidlertid gennem næsten hele 1800-tallet; i 1855 lå det på 1.191, og i 1901 havde byen 1.615 indbyggere. Væksten fortsatte indtil 1921, hvor tallet var 2.226. Stubbekøbings erhvervsliv nød da godt af stigende landbrugsproduktion i oplandet. Det var også af stor betydning, at byen fik en god havn i 1842, da dette bl.a. muliggjorde rutefart mellem Stubbekøbing og hhv. Vordingborg (1859) og København (1866). Stubbekøbing fik råd-, ting- og arresthus samt teknisk skole i 1860, sygehus i 1862 (afløst af et nyt i 1914), missionshus i år 1900 og handelsskole i 1914. Fra 1911 til 1966 var der jernbane mellem Stubbekøbing og Nykøbing F.
Siden 1920’erne havde Stubbekøbing til stadighed et befolkningstal på ca. 2.000-2.200. Den industri, som byen fik i 1800-tallet (jernstøberi, gasmålerfabrik, skibsbyggeri, brænderi og bryggeri m.m.), blev i 1900-tallet bl.a. suppleret med fiskeindustri. 1931-32 blev havnen udbygget med en vestlig del. I 1940 blev der etableret færgeforbindelse til Bogø.
Fra 1970 til 2006 var byen administrativt center for den nyoprettede Stubbekøbing Kommune. I denne periode fik byen en del servicevirksomheder, mens fiskerihavnen udviklede sig til en vigtig lystbådehavn. Indbyggertallet steg fra 2.031 i 1970 til 2.276 i 2006.