Store Heddinge voksede op omkring kirken Sankt Katharina fra ca. 1150. Bygherren kan have været kong Valdemar den Store, der havde kongsgård på Stevns. I 1261 havde byen fire møller og to gilder. Roskildebispen Peder Jensen Lodehat overtog i 1403 Hedding og Stevns Herred. Byens ældst kendte købstadsrettigheder stammer fra 1441.
Købstaden har heddet Store Heddinge siden begyndelsen af 1500-tallet. Byen havde vanskeligt ved at udvikle sig med sin beliggenhed et stykke fra kysten og hermed uden egen havn. Borgerne levede især af landbrug og salg af brændevin fra byens brænderier. Store Heddinge led under den svenske besættelse 1658-60 med opgjorte skader på 7.493 rigsdaler. Den beholdt sit landlige præg, og i 1787 havde den 565 indbyggere. I 1838 fik byen råd-, ting- og arresthus.
I 1855 var Store Heddinges indbyggertal steget til 1.231. Med anlæggelsen af Østsjællands Jernbane i 1879 fik byen station på banen. Købstaden fik sygehus og i 1890 både kommunekontor og fattiggård samt i 1896 kommuneskole med mellem- og realskole. 1896-97 byggede håndværkerforeningen en teknisk skole, og i år 1900 åbnede handelsskolen. I 1901 lå indbyggertallet på 1.816, og selv om landbruget fortsat var vigtigst, begyndte håndværk og småindustri at blive mere udbredt. Byen voksede efterhånden sammen med landsbyen Bjælkerup, og både småhuse og villaer skød op.
Med byudviklingen skete forandringer, bl.a. flyttede sygehuset i 1923 til det nybyggede amts- og bysygehus. De kulturelle tilbud udviklede sig også; i 1922 åbnede Stevns Folke bibliotek, og Stevns Museumsforening oprettede i 1926 Stevns Museum, der i 1950’erne flyttede til nye bygninger i landsbyen Højerup. Indbyggertallet faldt svagt, fra 2.532 i 1921 til 2.494 i 1950. Kommuneskolen havde indgået skoleforbund med Lille Heddinge og Frøslev Sogne. Sygehuset lukkede i 1964, og bygningerne blev derefter indrettet til plejehjem.
Store Heddinge blev administrativt center i den gamle Stevns Kommune i forbindelse med Kommunalreformen i 1970, og byen fik kommunens rådhus. Omkring biblioteket og Stevnshallen (1967) udfoldede byens sportsaktiviteter og foreningsliv sig. I 1970 lå befolkningstallet på 2.630, og dette var i 2006 steget til 3.419.
