Most organisms are exposed to the genotoxic chemical formaldehyde, either from endogenous or environmental sources. Therefore, biology has evolved systems to perceive and detoxify formaldehyde. The frmRA(B) operon that is present in many bacteria represents one such system. The FrmR protein is a transcriptional repressor that is specifically inactivated in the presence of formaldehyde, permitting expression of the formaldehyde detoxification machinery (FrmA and FrmB, when the latter is present). The X-ray structure of the formaldehyde-treated Escherichia coli FrmR (EcFrmR) protein reveals the formation of methylene bridges that link adjacent Pro2 and Cys35 residues in the EcFrmR tetramer. Methylene bridge formation has profound effects on the pattern of surface charge of EcFrmR and combined with biochemical/biophysical data suggests a mechanistic model for formaldehyde-sensing and derepression of frmRA(B) expression in numerous bacterial species.