Paleo-detectors offer a unique opportunity to probe the long-term history of cosmic ray flux, potentially revealing evidence of nearby supernovae and other high-energy astrophysical events. This technique relies on the persistent damage tracks left in natural minerals by nuclear recoils induced by cosmic ray secondaries, providing an integrated record of particle flux over geological timescales. In this contribution, we present our recently published work demonstrating that evaporites formed during the Messinian Salinity Crisis (~6 Myr ago) could provide an ideal natural archive for secondary cosmic ray interactions. By modeling the density of nuclear recoil tracks preserved in these minerals and taking into account the deposition and shielding rate in the geological event, we show that percent-level variations in the primary cosmic ray flux could be detected, extending the reach of paleo-detectors beyond dark matter and neutrino searches to cosmic ray paleo-astrophysics. We also introduce PRIµS, an INFN-funded experimental effort that is the natural extension of our phenomenological work. Using high-throughput optical microscopy and plasma etching techniques, PRIµS aims to analyze a variety of samples, with a focus on halite and other evaporites, with the goal of validating theoretical models and refining background estimates for future paleo-detector applications.