Stevns Kommune gemmer på et væld af sagn og fortællinger. Den måske vigtigste fortælling er den om Klintekongen eller Ellekongen/Elverkongen, for i nogle fortællinger er det én og samme konge, mens det i andre er forskellige. Han hersker over klinterne på Stevns, Møn og Rügen og rejser i en vogn, der bliver trukket af fire sorte heste. Han rejser over havet, der bliver mørkt og vildt, mens man hører hestenes vrinsken.
I skuespillet Elverhøi af Johan Ludvig Heiberg kaldes Klintekongen for Elverkongen. Ifølge myten har en dansk konge aldrig besøgt Stevns (ud over i Heibergs skuespil), for på Stevns hersker kun én konge, og det er Klintekongen. Klintekongen bor dels i sit kammer i Store Heddinge Kirke, dels i sin hule i Møns Klint. Han har også sat sit aftryk i kommunevåbenet, som viser Klintekongens krone over Stevns Klint.
Der er adskillige myter om Højerup Gamle Kirke, som ligger på kanten af Stevns Klint. En af dem handler om en skipper i havsnød. Han afgav det løfte, at han ville bygge en kirke, hvis han kom sikkert i land. Han holdt løftet, men kirken ligger så yderligt, at den er i fare for at styrte i havet, hvorfor den hvert år ved julenat siges at flytte sig et hanefjed ind i landet. Det var dog ikke helt nok, for d. 16. marts 1928 styrtede kirkens kor i havet.
Ved Ranes Banke ved Varpelev rider adelsmanden Rane Jonsen hver nat hovedløs rundt. Han blev dømt fredløs for sin medvirken til mordet på kong Erik Klipping i Finderup Lade. Han blev fanget i 1294 og henrettet. Jonsen forbindes i øvrigt til Gjorslev Gods.
