Stege opstod antagelig i ly af den kongelige borg, Stegeborg, der omkring år 1200 blev anlagt ud til det smalle sund mellem Stege Bugt og Stege Nor. Stegeborg blev senere renoveret af kong Erik Menved. De ældst kendte købstadsprivilegier stammer fra 1268. Centralt beliggende i forhold til den stærkt benyttede indre sejlrute fra Storebælt til Østersøen havde Stege i middelalderen gode vækstbetingelser. Handel og deltagelse i sildemarkederne i Skanør og Falsterbo var i høj grad medvirkende til, at Stege udviklede sig til en særdeles velstående by, der ved udgangen af middelalderen hørte til blandt landets større købstæder. Det antages, at der da var ca. 2.500 indbyggere. Denne velstand afspejlede sig i Steges store Sankt Hans Kirke og andre nu forsvundne gejstlige og verdslige bygninger.
Storegade har altid været byens hovedgade, og ved udgravninger kan der findes vejbelægninger fra før år 1400. Ligeledes findes der næsten overalt op til 2,5 m tykke kulturlag. Enkelte steder er der foretaget arkæologiske udgravninger, hvor dele af huskonstruktioner og gulve er fremkommet. De ældste er dateret til begyndelsen af 1300-tallet, bl.a. på Gåsetorvet, hvor der er fundet middelaldertomter og muligvis resterne af en handelsbod.
Portene mod nord og voldgraven blev opført i begyndelsen af 1400-tallet, men byen er først vokset ud til porten efter middelalderens afslutning. Før den brede voldgrav blev opført, har byen haft en mindre grav nord for Møllebrøndstræde som nordlig afslutning.
Da sildemarkederne fik mindre betydning fra midten af 1500-tallet, forsvandt fundamentet for Steges velstand. Denne tilbagegang fortsatte i 1600- og 1700-tallet som følge af byens begrænsede opland og de lokale bønders ulovlige handel uden om købstaden. Derudover hærgedes byen af brande i 1700-tallet. I 1787 boede der kun 829 indbyggere i Stege. Først med øget kornsalg og en uddybning af sejlløbet blev de økonomiske vilkår i den første halvdel af 1800-tallet så forbedrede, at Steges folketal mere end fordobledes frem mod 1845, hvor det lå på 1.761.
Med industrialiseringen undergik Stege i den sidste halvdel af 1800-tallet og de første årtier af det følgende århundrede en betydelig vækst. Der blev oprettet mange mindre industrivirksomheder, og i 1884 åbnede De Danske Sukkerfabrikker et stort fabriksanlæg med egen sidehavn. Fabrikken udviklede sig til at blive Møns største virksomhed. Sammen med væksten i de øvrige byerhverv betød det, at indbyggertallet mellem 1855 og 1916 voksede fra 1.934 til 2.186. Det omfattende erhvervs- og boligbyggeri efter ca. 1850 førte til betydelig bebyggelsesmæssig fortætning i den ældre by og dannelsen af to brokvarterer uden for denne. Det ene opstod i Lendemarke på den anden side af farvandet med små karrédannelser tæt ved sukkerfabrikken og med mindre fabriksanlæg samt gadehuse og villaer. Det andet voksede frem uden for de gamle byvolde med store villaer ud til bugten og noret og en mere spredt bebyggelse med gadehuse omkring kommunens nye gasværk fra 1910.
Fra 1920 ekspanderede både sukkerfabrikken og andre af byens industrier og øvrige erhvervsvirksomheder, og indbyggertallet nåede i 1950 op på 3.735. Der opstod mindre yderdistrikter uden for brokvartererne, bl.a. på østsiden af vejen til Ulvshale, hvortil Karen Volfs kagefabrik (i dag: Bisca A/S) flyttede i 1968. Steges to yderdistrikter udvidedes samtidig med større villakvarterer. Den begyndende velfærdsstat manifesterede sig her med bl.a. alderdomshjem (1925), kommuneskole (1935) og aldersrenteboliger (1938).
I 1968 blev Stege administrativt center for den nyetablerede Møn Kommune. I de sidste årtier af 1900-tallet satte velfærdsstaten endnu flere spor i Steges bybillede. Mønshallen åbnede i 1971, og i 1980 fulgte Møns Svømmehal. Der skete et omfattende plejehjems- og boligbyggeri, og flere daginstitutioner åbnede. Indvielsen af Farøbroen i 1985 førte til en øget turisme på øen og hermed i Stege. Sukkerfabrikken lukkede i 1989, og området har siden tjent erhvervsmæssige og kulturelle formål. I 2005 lukkede Stege Sygehus. Indbyggertallet, som i 1970 havde ligget på 3.869, stagnerede frem mod år 2000; i 2006 lå det på 4.043.
