DNA cytosine methylation is an epigenetic mark that promotes gene silencing and performs critical roles during reproduction and development in both plants and animals. The genomic distribution of DNA methylation is the dynamic outcome of opposing methylation and demethylation processes. In plants, active demethylation occurs through a base excision repair pathway initiated by 5-methycytosine (5-meC) DNA glycosylases of the REPRESSOR OF SILENCING 1 (ROS1)/DEMETER (DME) family. To gain insight into the mechanism by which Arabidopsis ROS1 recognizes and excises 5-meC, we have identified those protein regions that are required for efficient DNA binding and catalysis. We have found that a short N-terminal lysine-rich domain conserved in members of the ROS1/DME family mediates strong methylation-independent binding of ROS1 to DNA and is required for efficient activity on 5-meC.G, but not for T.G processing. Removal of this domain does not significantly affect 5-meC excision from short molecules, but strongly decreases ROS1 activity on long DNA substrates. This region is not required for product binding and is not involved in the distributive behavior of the enzyme on substrates containing multiple 5-meC residues. Altogether, our results suggest that methylation-independent DNA binding allows ROS1 to perform a highly redundant search for efficient excision of a nondamaged, correctly paired base such as 5-meC in long stretches of DNA. These findings may have implications for understanding the evolution of structure and target specificity in DNA glycosylases.