Methylation of cytosine to 5-methylcytosine (5mC) is important for gene expression, gene imprinting, X-chromosome inactivation, and transposon silencing. Active demethylation in animals is believed to proceed by DNA glycosylase removal of deaminated or oxidized 5mC. In plants, 5mC is removed from the genome directly by the DEMETER (DME) family of DNA glycosylases. Arabidopsis thaliana DME excises 5mC to activate expression of maternally imprinted genes. Although the related Repressor of Silencing 1 (ROS1) enzyme has been characterized, the molecular basis for 5mC recognition by DME has not been investigated. Here, we present a structure-function analysis of DME and the related DME-like 3 (DML3) glycosylases for 5mC and its oxidized derivatives. Relative to 5mC, DME and DML3 exhibited robust activity toward 5-hydroxymethylcytosine, limited activity for 5-carboxylcytosine, and no activity for 5-formylcytosine. We used homology modeling and mutational analysis of base excision and DNA binding to identify residues important for recognition of 5mC within the context of DNA and inside the enzyme active site. Our results indicate that the 5mC binding pocket is composed of residues from discrete domains and is responsible for discrimination against 5mC derivatives, and suggest that DME, ROS1, and DML3 utilize subtly different mechanisms to probe the DNA duplex for cytosine modifications.