Byen voksede op omkring borgen Stegehus fra Valdermar den Stores tid. Frem til 1246 var Jakob Sunesen høvedsmand på Stegehus og formentlig ansvarlig for opførelsen af Stege Kirke. Erik 4. Plovpenning holdt i 1247 sin halvbror Knud af Blekinge fanget på Stegehus, men han blev befriet af lübeckerne. Omkring 1252 sad en af lübeckernes allierede, den tyske ridder Henrik Æmeltorp som høvedsmand på borgen og i 1290 en anden tysk adelig, Hintze Halkenhagen.

Stege blev under Erik 5. Klipping købstad i 1268.

I 1310 kom borgen atter under kronen, men ved Danmarks pantsætning under den kongeløse tid var Stege besat af tyske pantejere. Valdemar 4. Atterdag fik i 1348 indløst Møn og Falster og overdraget Stegehus, og han var formentlig ansvarlig for en udbygning af borgen. Høvedsmænd på Stegehus var Henning Moltke 1323, Fikke Moltke 1362, rigsråd Jens Rud 1396-1401, Valdemar Bydelsbak 1419, grev Vitslav af Eberstein, Erik Aagesen Thott 1457-64, Laurens Axelsen Thott 1465, Axel Valkendorf 1480, Vincens Iversen Dyre 1485, Mogens Gøye 1500 og Jørgen Rud 1503.

En vold omkring Stege blev gravet i slutningen af 1400-tallet, og voldgraven fyldt med vand. Der var en mur langs voldgraven og tre tårne med porte og vindebro. Den ene port er den bevarede Mølleport (se nedenfor), mens de to andre lå ud for Langestræde og Rådhusstræde (tidligere Skammestræde).

I Fra 1505 forlenedes Stegehus til Anders Bentsen Bille under hvem voldanlægget i 1510 fik sin ilddåb, idet lübeckerne forsøgte at indtage Stege. Det mislykkede, men Møns anden købstad, Borre, blev lagt øde. Men Bille, som havde støttet Frederik 1., måtte i 1534 bortrejst se Stegehus erobret, plyndret og nedrevet af Steges borgere, som støttede Christian 2.. Af grev Christoffer havde Stege-borgerne som belønning fået Ulvshale, men Christian 3. tog dette igen, og borgernes ledere blev henrettet.

I 1540 brændtes i Stege den første kvinde i Danmark dømt som heks.

I 1557 blev Stegehus og Møn forlenet til Niels Truidsen Ulfstand til Barsebæk, som mistede det som følge af gæld i 1563 og kun kortvarigt fik det igen i 1566.

En bemærkelsesværdig retssag fandt sted i Stege i 1567. Den ny præst Iver Bertelsen trolovede sig med enken efter den tidligere præst for at sikre sig embedet, men ville ikke gifte sig med hende. Han udelod tilmed eksorcismen fra dåbsritualet. Han blev derfor dømt til døden; men straffen blev dog senere ændret til livstidsfængsel og fortabelse af gods.

I 1634 blev Corfitz Ulfeldt lensmand på Stegehus. Da Ulfeldt udnævntes til Rigsrådet 1636, blev han gift med Leonora Christina og boede på Møn 1636-1637.

Da Sverige genoptog angrebet mod Danmark efter freden i Roskilde 1658, blev Møn i 1659 via Bogø besat. Møn blev plyndret, men Stege undgik de værste ødelæggelser ved at betale en kontant sum. Øen var besat af Sverige frem til 1660, og udplyndringen var starten på en lang nedgangstid, der også ramte Stege hårdt. I 1672 havde Stege kun 656 indbyggere.

Møn blev i 1664 pantsat til hollænderen Gabriel Marselis, men kongen beholdt Stege by.

En stor del af bymuren og 2 byporte blev nedrevet under Samuel Christoph von Plessen 1685-1697, som anvendte materialerne til opførelsen af Nygårde (nu Marienborg).

Byens grundplan stammer fra middelalderen, og byens mølleport er fra slutningen af 1400-tallet. Ved siden af mølleporten ligger Empiregården, som er en købmandsgård fra 1813, som siden 1958 har rummet Møns Museum.

Nær Stege Kirke er en gammel latinskole med murværk fra 1400-tallet. På torvet ligger Kammerrådsgårdën. som er en gulkalket købmandsgård fra 1770'erne opført for Kammerråd Puttfercken. I 1881 overtog købmandsslægten Carøe ejendommen. Overfor er apoteket, som er en nyklassicistisk bygning fra omkring 1799. Det tidligere rådhus på torvet er i renæssancestil efter tegninger af M.G.B. Bindesbøll fra 1854. På torvet ligger også en bygning, der, som facaden afslører, tidligere var sæde for Møns Spare- og Laanekasse, men som i dag huser en advokatforretning.

Ved havnen ligger købmandsgården Hages Gård fra 1799 og en toldbod fra 1848. På den vestlige side af havnen mod Lendemarke åbnede i 1884 De Danske Sukkerfabrikker en fabrik, hvis bygninger i dag huser en række forskellige mindre virksomheder.

Der er i dag intet at se af Stegeborg, men voldanlægget om Stege er bevaret som Danmarks eneste middelalderlige byvold. Stege ligger på en tange, og volden skærmer byen på landsiden mod øst fra kyst til kyst.

* Stege Sogn * Stegehus Len * Stege Bugt