Under Sparresholm findes rester af den middelalderlige ringmursborg Padeborg, ved hvilken der i midten af 1300-tallet udspillede sig dramatiske scener. Den nuværende hovedbygning fra 1600-tallet, der blev voldsomt raseret af en brand i 2013, er opført på en lav banke, der omgives af rester af en voldgrav. Ved en udgravning i kældrene og på gårdspladsen foretaget af Nationalmuseet i 1958 blev der for første gang påtruffet murrester fra middelalderborgen Padeborg.
Den ældste borg, der formodes opført i 1200-tallet, har bestået af en ringmur omkring en uregelmæssig firkantet borggård. Ringmuren var ca. 1,2 m tyk og opført af tilhuggede kampesten. Langs indersiden af den sydlige ringmur lå borgens palatium, borgherrens stenbyggede bolig. På et tidspunkt blev palatiet erstattet af en ny, teglbygget bygning med kraftige mure, formentlig et tårn. Udgravningen viste bl.a., at det formodede tårn sandsynligvis blev ødelagt ved en brand. I brandlaget fandtes tre mønter slået under Christoffer 2., der regerede i hhv. 1319‑26 og 1329‑32. Borgen omtales dog først i de skriftlige kilder i 1334. Det vides også, at i 1343 blev Aarhusbispen og degnen i Roskilde taget til fange og ført til Padeborg som fanger. Blot to år senere blev borgen erobret af kong Valdemar Atterdag, som sandsynligvis nedbrændte den ved denne lejlighed.
