The ability to induce heritable genomic changes in response to environmental cues is valuable for environmental biosensing, for experimentally probing microbial ecology and evolution, and for synthetic biology applications. Site-specific recombinases provide a route to genetic memory via targeted DNA modifications, but their high specificity and efficiency are offset by leaky expression and limited tunability in prokaryotes. We developed a tightly regulated, titratable Cre recombinase system for Escherichia coli that achieves low recombination rates and minimal basal activity. Implemented on both plasmids and the chromosome, the latter showed superior retention of genetic memory across generations. These features make the system broadly useful for environmental biosensing and other applications. To demonstrate applicability to environmental biosensing, we developed a whole-cell recombination-based biosensor for arsenite, a toxic and ubiquitous pollutant that is primarily mobilized in anoxic environments such as flooded soils, sediments, and aquifers. However, existing arsenite whole-cell biosensors face limitations in sensitivity and workflow in anaerobic settings. Our biosensor reliably recorded anoxic arsenite exposure as a stable genetic memory for delayed fluorescence readout in aerobic conditions, with detection sensitivity comparable to conventional wet chemical methods. By decoupling exposure from measurement, this approach offers a foundation for arsenite biosensing under field-relevant conditions, including redox variability and other physicochemical gradients, without the constraints of anoxic measurement. More broadly, the ability to induce low-rate, heritable genetic changes expands the genetic toolkit for environmentally responsive systems, with applications in environmental monitoring, bioproduction, bioengineering, as well as experimental studies of microbial ecology, evolution, and host-microbe interactions.