A large experimental program is underway to extend the sensitivity of direct detection experiments, searching for interactions 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.