Arkitekturen i Store Heddinge er præget af den lokale kridtsten, som især har sat sit præg på huse opført mellem 1860 og 1930. Byens vandtårn er bygget af kridtsten over en sokkel af røde munkesten og er fra 1911. Det er tegnet af G.B. Hagen.
Mange af husene i Algade er fra 1800-tallet med en kombination af længehuse og mindre gårdanlæg bagved. Gaden har 2010-13 fået ny udformning af GHB Landskab (siden 2020 LYTT Architecture).
Den ældre del af byen består af en- eller toetagers byhuse, hvor enkelte bygninger er bevaret med ældre bygningsdetaljer. Det er især værd at fremhæve byens tidligere råd-, ting- og arresthus opført 1832-38 og tegnet af Jørgen Koch. Bygningen lejes af Stevns Kommune og rummer bl.a. mødefaciliteter, der lejes ud til lokale virksomheder og foreninger. Sprøjtehuset og ringmurene er tegnet af den lokale arkitekt Georg Kretz.
De mere anonyme huse er opført i mange forskellige materialer, og der ses både mursten, bindingsværk og kridtsten, hvor Østergade 14 og Nørregade 13 begge er eksempler på blandingen af den hvide kridtsten og den røde mursten. I nyere tid har opførelsen af mange parcelhuse sat sit præg på byen, fx langs indfaldsvejen Vesterbro.