We review the abundance and diversity of terrestrial rock hosted life, the environments it inhabits, the evolution of its metabolisms, and its fossil biomarkers to provide guidance in the search for the biomarkers of rock hosted life on Mars. Key finds are metabolic pathways for chemolithotrophic microorganisms evolved much earlier in Earth history than those of surface dwelling phototrophic microorganisms,the emergence of the former occurred at a time when Mars was habitable, whereas that of the latter occurred at a time when the martian surface would have been uninhabitable, subsurface biomass do not correlate with organic carbon and tends to be highest at interfaces where chemical redox gradients are most pronounced, deep subsurface metabolic activity does not rely upon the respiration of organic photosynthate but upon the flux of inorganic energy and the abiotic and biotic recycling of metabolic waste products, and the rock record reveals examples of subsurface life back to 3.45 Ga with several examples of good preservation potential in rock types that are quite different from those preserving the photospheric supported biosphere.These findings suggest that rock hosted life would have likely to emerge and be preserved in a martian context. We thus propose a Mars exploration strategy that scales spatially, focusing initially on identifying rocks with evidence for groundwater flow and low temperature mineralization, then identifying redox and permeability interfaces preserved within rock outcrops, and finally focusing on finding minerals associated with redox reactions and traces of carbon and diagnostic biosignatures. The lessons from Earth show that ancient rock hosted life is preserved in the fossil record and confirmable via a suite of morphologic, organic, mineralogical and isotopic fingerprints and microscopic textures.