A large experimental program is underway to extend the sensitivity of direct detection experiments, searching for the interaction of Dark Matter with nuclei, down to the neutrino floor. However, such experiments are becoming increasingly difficult and costly due to the large target masses and exquisite background rejection needed for the necessary improvements in sensitivity. We investigate an alternative approach to the detection of Dark Matter-nucleon interactions: Searching for the persistent traces left by Dark Matter scattering in ancient minerals obtained from much deeper than current underground laboratories. We estimate the sensitivity of paleo-detectors, which extends far beyond current upper limits for a wide range of Dark Matter masses.