Micron-sized cavities created by the actions of rock-etching microorganisms known as euendoliths are explored as a biosignature for life on early Earth and perhaps Mars. Rock-dwelling organisms can tolerate extreme environmental stresses and are excellent candidates for the colonization of early Earth and planetary surfaces. Here, we give a brief overview of the fossil record of euendoliths in both sedimentary and volcanic rocks. We then review the current understanding of the controls upon the distribution of euendolithic microborings and use these to propose three lines of approach for testing their biogenicity: first, a geological setting that demonstrates a syngenetic origin for the euendolithic microborings; second, microboring morphologies and distributions that are suggestive of biogenic behavior and distinct from ambient inclusion trails; and third, elemental and isotopic evidence suggestive of biological processing. We use these criteria and the fossil record of terrestrial euendoliths to outline potential environments and techniques to search for endolithic microborings on Mars.