Targeted methylation of cytosine residues by S-adenosylmethionine-dependent DNA methyltransferases modulates gene expression in vertebrates. Here we show that cytosine-5-methyltransferases catalyze reversible covalent addition of exogenous aliphatic aldehydes to their target residues in DNA, thus yielding corresponding 5-hydroxyalkylcytosines. Such atypical enzymatic reactions with non-cofactor-like substrates open new ways for sequence-specific derivatization of DNA and demonstrate enzymatic exchange of 5-hydroxymethyl groups on cytosine in support of an oxidative mechanism of DNA demethylation.