Cells produce considerable genotoxic formaldehyde from an unknown source. We carry out a genome-wide CRISPR-Cas9 genetic screen in metabolically engineered HAP1 cells that are auxotrophic for formaldehyde to find this cellular source. We identify histone deacetylase 3 (HDAC3) as a regulator of cellular formaldehyde production. HDAC3 regulation requires deacetylase activity, and a secondary genetic screen identifies several components of mitochondrial complex I as mediators of this regulation. Metabolic profiling indicates that this unexpected mitochondrial requirement for formaldehyde detoxification is separate from energy generation. HDAC3 and complex I therefore control the abundance of a ubiquitous genotoxic metabolite.