Reactive aldehydes arise as by-products of metabolism and are normally cleared by multiple families of enzymes. We find that mice lacking two aldehyde detoxifying enzymes, mitochondrial ALDH2 and cytoplasmic ADH5, have greatly shortened lifespans and develop leukemia. Hematopoiesis is disrupted profoundly, with a reduction of hematopoietic stem cells and common lymphoid progenitors causing a severely depleted acquired immune system. We show that formaldehyde is a common substrate of ALDH2 and ADH5 and establish methods to quantify elevated blood formaldehyde and formaldehyde-DNA adducts in tissues. Bone-marrow-derived progenitors actively engage DNA repair but also imprint a formaldehyde-driven mutation signature similar to aging-associated human cancer mutation signatures. Furthermore, we identify analogous genetic defects in children causing a previously uncharacterized inherited bone marrow failure and pre-leukemic syndrome. Endogenous formaldehyde clearance alone is therefore critical for hematopoiesis and in limiting mutagenesis in somatic tissues.