AlkB is a DNA/RNA repair enzyme that removes base alkylations such as N1-methyladenosine (m1A) or N3-methylcytosine (m3C) from DNA and RNA. The AlkB enzyme has been used as a critical tool to facilitate tRNA sequencing and identification of mRNA modifications. As a tool, AlkB mutants with better reactivity and new functionalities are highly desired; however, previous identification of such AlkB mutants was based on the classical approach of targeted mutagenesis. Here, we introduce a high-throughput screening method to evaluate libraries of AlkB variants for demethylation activity on RNA and DNA substrates. This method is based on a fluorogenic RNA aptamer with an internal modified RNA/DNA residue which can block reverse transcription or introduce mutations leading to loss of fluorescence inherent in the cDNA product. Demethylation by an AlkB variant eliminates the blockage or mutation thereby restores the fluorescence signals. We applied our screening method to sites D135 and R210 in the Escherichia coli AlkB protein and identified a variant with improved activity beyond a previously known hyperactive mutant toward N1-methylguanosine (m1G) in RNA. We also applied our method to O6-methylguanosine (O6mG) modified DNA substrates and identified candidate AlkB variants with demethylating activity. Our study provides a high-throughput screening method for in vitro evolution of any demethylase enzyme.