The Martian surface is cold, dry, exposed to biologically harmful radiation and apparently barren today. Nevertheless, there is clear geological evidence for warmer, wetter intervals in the past that could have supported life at or near the surface. This evidence has motivated National Aeronautics and Space Administration and European Space Agency to prioritize the search for any remains or traces of organisms from early Mars in forthcoming missions. Informed by (1) stratigraphic, mineralogical and geochemical data collected by previous and current missions, (2) Earth's fossil record, and (3) experimental studies of organic decay and preservation, we here consider whether, how, and where fossils and isotopic biosignatures could have been preserved in the depositional environments and mineralizing media thought to have been present in habitable settings on early Mars. We conclude that Noachian‐Hesperian Fe‐bearing clay‐rich fluvio‐lacustrine siliciclastic deposits, especially where enriched in silica, currently represent the most promising and best understood astropaleontological targets. Siliceous sinters would also be an excellent target, but their presence on Mars awaits confirmation. More work is needed to improve our understanding of fossil preservation in the context of other environments specific to Mars, particularly within evaporative salts and pore/fracture‐filling subsurface minerals.