Sostrup er en vandborg, bygget på en menneskeskabt ø af kampesten og hundredvis af egetræspæle. Pælene skal bevare fugten, så de ikke bliver porøse. Derfor er det vigtigt, at voldgraven aldrig tørrer ud.
Et gammelt sagn fortæller, at Sostrup slot vil styrte i voldgraven en julenat. Det skulle den tidligere ejer af Sostrup, Jørgen Scheel - også kendt under navnet Den vilde greve - ikke nyde noget af, og derfor byggede han et hus i den nærliggende by Gjerrild, som han kunne overnatte i netop julenat. Huset kaldte han Kokkehuset, og det ligger der endnu.
Mange adelsfamilier har tidligere ejet Sostrup. Den magtfulde Scheel-familie ejede slottet fra 1612 i 211 år. Dengang hed slottet Skeel efter den oprindelige måde at stave familiens navn på. Det sidste medlem af Scheel-familien, der ejede slottet, var Jørgen Scheel, Den vilde greve. Han rejste rundt i Europa på flere studieture i løbet af en 15 år lang periode, hvor han bragte kulturelle strømninger med hjem til Sostrup: Kunstværker, 11.600 bøger, møbler, håndmalede tapeter osv.
I 1960 overtog en gruppe af cisterciensernonner slottet og omdannede det til et kloster. I 1992 blev det både Maria Hjerte Kloster og Maria Hjerte Kirke bygget under ledelse af abbedisse Theresa Brenninkmeijer. Abbedissen og 26 nonner forlod i 2013 klosteret og Danmark.