DNA methylation at cytosine bases (5-methylcytosine, 5mC) is a heritable epigenetic mark regulating gene expression. While enzymes that metabolize 5mC are well-characterized, endogenous signaling molecules that regulate DNA methylation machinery have not been described. We report that physiological nitric oxide (NO) concentrations reversibly inhibit the DNA demethylases TET and ALKBH2 by binding to the mononuclear non-heme iron atom forming a dinitrosyliron complex (DNIC) and preventing cosubstrates from binding. In cancer cells treated with exogenous NO, or endogenously synthesizing NO, 5mC and 5-hydroxymethylcytosine (5hmC) increase, with no changes in DNA methyltransferase activity. 5mC is also significantly increased in NO-producing patient-derived xenograft tumors from mice. Genome-wide methylome analysis of cells chronically treated with NO (10 days) shows enrichment of 5mC and 5hmC at gene-regulatory loci, correlating with altered expression of NO-regulated tumor-associated genes. Regulation of DNA methylation is distinctly different from canonical NO signaling and represents a unique epigenetic role for NO.