En hovedbygning fra Grevens Fejde blev revet ned omkring 1715, og ikke genopført, da godset blev drevet sammen med Gjorslev. En hovedbygning for forpagteren blev opført i 1828, men nedrevet i 1946.
Stedet tilhørte i 1346 væbneren Niels Eriksen Saltensee af Linde, men blev sammen med byen Sørup solgt eller givet til Niels Knudsen af Svanholm (død mellem 1365-66) i forbindelse med Niels Knudsens ægteskab med Niels Eriksens datter Cecilie. Efter Niels Knudsens død ejedes Søholm af Cecilies bror Erik Nielsen. Hans enke Ingeborg Pedersdatter Grubbe blev gift 2. gang med Johan Olufsen Bjørn, der senere kaldte sig af Søholm. Efter hans død gik stedet til hans døtre Hille (død 1451) og Helene (død 1451) gift med Steen Basse til Tybjerg, som købte hele Søholm. Da han døde barnløs, gik godset til hans søsters datter Sidsel Ovesdatter Lunge, senere hofmesterinde hos dronning Christine, og hendes mand, rigsråd Tobern Bille.
Ejendommen gik formentlig 1464 over til sønnen Bent Bille (død 1494). Hans enke Ermegård Eggertsdatter Frille blev boende med sønnen Anders Bentsen Bille, der 1504-1510 kaldte sig af Søholm, men først lidt efter lidt udkøbte sine søskende af godset. I 1523 blev han rigsråd og fik Stevns Herred som pantelen. Ved udbruddet af Grevens Fejde tog han først parti mod Grev Christoffer, men blev omringet på Søholm, overgav sig og sluttede sig til greven. Christian 3. tog Søholm fra ham, men han fik det i 1536 igen. Formentlig var bygningerne da nedrevet, og han opførte det Søholm, der stod til omkring 1715. Efter hans død brugte sønnerne Hans og Frands "til Søholm" i deres navn. Sidstnævntes søn, Erik Bille, arvede Søholm, men døde ugift i 1590.
