Skjoldenæsholm Voldsted er anlagt for enden af en smal tange i Valsølille Sø. Borgen lå tæt ved en nu forsvundet del af Kong Valdemars Vej på det middelalderlige vejnet. Voldstedet måler ca. 150 x 200 m og består af to borgbanker omgivet og adskilt af 8 m høje voldgrave, der igen omgives af en delvis bevaret ringvold.
Borgen kendes tilbage fra 1200-tallet og menes også at være ældre. Da Christoffer 2. lod borgen pantsætte til en holstener før sin død i 1332, kan Skjoldenæsholm oprindelig have haft en kongelig bygherre. I 1340’erne vandt kong Valdemar Atterdag borgen tilbage til kongemagten. Senere kom borgen i privat eje, men blev igen ejet af kronen i 1429 under kong Erik af Pommern.